Функція Ейлера
Функція Ейлера , де — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за і взаємно простих з ним.[1]
Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:
де — просте число.
Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритма шифрування RSA.
Деякі значення функціїРедагувати
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
---|---|---|---|---|---|---|---|---|---|---|
0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |
ВластивостіРедагувати
- , якщо — просте число;[2]
- , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна;[3]
- , якщо і взаємно прості. Докладніше: Теорема Ейлера.[4]
- , , , якщо — найменше спільне кратне, a — найбільший спільний дільник.
Асимптотичні відношенняРедагувати
- де — деяка константа;
Комп'ютерна реалізаціяРедагувати
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
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
Код вище при n= 6, 9... видає неправильний результат. Перевірено для Python 3.11 у Visual Studio Code
Наступний код працює коректно:
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
Див. такожРедагувати
ПриміткиРедагувати
- ↑ Ribenboim, 1996, с. 34(англ.).
- ↑ Сагалович, 2007, с. 35—36, Вычисление функции Эйлера(рос.).
- ↑ Burton, 2007, с. 133, Theorem 7.2(англ.).
- ↑ Чандрасекхаран. Введение в аналитическую теорию чисел, 1974 (рос.).
ПосиланняРедагувати
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |