Топ питань
Часова шкала
Чат
Перспективи

Функція Ейлера

З Вікіпедії, вільної енциклопедії

Функція Ейлера
Remove ads

Функція Ейлера , де  натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за і взаємно простих з ним. Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:

Thumb
Перша тисяча значень

де  просте число.

Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритму шифрування RSA.

Remove ads

Деякі значення функції

Більше інформації ...
Remove ads

Властивості

  1. , якщо  — просте число;[1]
  2. , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна;[2]
  3. , якщо і взаємно прості. Докладніше: Теорема Ейлера.[3]
  4. , , , якщо  найменше спільне кратне, a  найбільший спільний дільник.
Remove ads

Асимптотичні відношення

  1. де  — деяка константа;

Комп'ютерна реалізація

C++

Код на мові C++
int phi(int n) {
	int ret = 1;
	for(int i = 2; i * i <= n; ++i) {
		int p = 1;
		while(n % i == 0) {
			p *= i;
			n /= i;
		}
		if((p /= i) >= 1) ret *= p * (i - 1);
	}
	return --n ? n * ret : ret;
}

Pascal

Код на мові Pascal
function gcd (A,B: longint): longint;
begin
  while (A <> B) do
  begin
    if (A > B) then 
      Dec(A, B)
    else 
      Dec(B, A);
  end;
  gcd := A;
end;

var
  N: longint;
  I,A: longint;

begin
  WriteLn ('Input N: ');
  ReadLn (N);
  A := 0;
  for I := 1 to N-1 do
    if (gcd(I, N) = 1) then
      Inc (A);
  WriteLn ('The Euler Function of N is: ', A);
  ReadLn;
end.

Python

Код на мові Python
def euler_function(n):
    ret = 1
    i = 2
    while i*i <= n:
        p = 1
        while not n % i:
            p *= i
            n //= i
        p //= i
        if p >= 1:
            ret = ret * p * (i - 1)
        i += 1
    n -= 1
    return n * ret if n else ret

Ruby

Код на мові Ruby
def euler_function(n):
    ret = 1
    for i in range(2, math.floor(n**0.5)):
        p = 1
        while not n % i:
            p *= i
            n /= i
        p /= i
        if p >= 1:
            ret = ret * p * (i - 1)
    n -= 1
    return n * ret if n else ret
Remove ads

Див. також

Примітки

Посилання

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads