Алгоритмы: Функция Эйлера | C++

Определение

Функция Эйлера phi (n) — это количество чисел от 1 до n, взаимно простых с n. Иными словами, это количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице.
phi (1)=1,
phi (2)=1,
phi (3)=2,
phi (4)=2,
phi (5)=4.

Свойства

Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
  1. Если p — простое число, то phi (p)=p-1.
(Это очевидно, т.к. любое число, кроме самого p, взаимно просто с ним.)
  1. Если p — простое, a — натуральное число, то phi (p^a)=p^a-p^{a-1}.
  1. Если a и b взаимно простые, то phi(ab) = phi(a) phi(b) ("мультипликативность" функции Эйлера).

Реализация

Простейший код C++, вычисляющий функцию Эйлера,
факторизуя число элементарным методом за 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;
}


Views: 677

Комментарии пока отсутcтвуют.