Phi Function – 3
Euler’s Totient Function (N), also known as the phi function, computes the number of integers less than equal to N that is also coprime to N. Two numbers are coprime if their GCD equals 1.
First note that if some integer P is prime, then (P) = P – 1
Also note that if P is prime then (pk) =pk-pk-1
Finally, the Euler totient function is multiplicative meaning that (ab) = (a) * (b)
There exists a general formula for (N). Assume N = p1k1 * p2k2…paka
Then (N) = N * (1-1/p1)*(1-1/p2) …. (1-1/pa).
It is easy to see that this is true using the properties shown above.
Using this, we can compute (N) in sqrt(N) naively by finding the prime factorization of N.
However using a sieve, we can compute (N) for all N in the range 1 to N in O(NloglogN) time.
| void phi(int N){ vector<int> p(N+1); for(int i = 0; i <= N; i++){ p[i] = i; } for(int i = 2; i <= N; i++){ if(p[i] == i){ for(int j = i; j <= N; j += i){ p[j] -= p[j]/i; } } } } |
It’s not hard to see why this is equivalent to the formula provided above.
Euler’s theorem states that
a(n)=1 (mod n) if a and n are coprime