Euler's totient function

general
,
1

can anyone provide me with efficient algorithm to calculate totient function with explanation?

2

The best i know is 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;
}

Taken from e-maxx.

phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pk)
Where p1, …, pk are the prime factors of the number n.

2 Likes