ALGORITHMS
Определение
Функция Эйлера phi (n) — это количество чисел от 1 до n, взаимно простых с n. Иными словами, это количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице.
phi (1)=1,
phi (2)=1,
phi (3)=2,
phi (4)=2,
phi (5)=4.
phi (2)=1,
phi (3)=2,
phi (4)=2,
phi (5)=4.
Свойства
Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
- Если p — простое число, то phi (p)=p-1.
- Если p — простое, a — натуральное число, то phi (p^a)=p^a-p^{a-1}.
- Если a и b взаимно простые, то phi(ab) = phi(a) phi(b) ("мультипликативность" функции Эйлера).
Реализация
Простейший код C++, вычисляющий функцию Эйлера,
факторизуя число элементарным методом за O(sqrt n):
факторизуя число элементарным методом за O(sqrt n):
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}