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

де — просте число.
Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритму шифрування RSA.
Remove ads
Деякі значення функції
Remove ads
Властивості
- , якщо — просте число;[1]
- , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна;[2]
- , якщо і взаємно прості. Докладніше: Теорема Ейлера.[3]
- , , , якщо — найменше спільне кратне, a — найбільший спільний дільник.
Remove ads
Асимптотичні відношення
- де — деяка константа;
Комп'ютерна реалізація
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
Див. також
Примітки
Посилання
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads