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

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