Euler's Phi function.
Returns the value of Euler's phi function for n. It basically calculates the number of relative prime integers to n smaller than n.
This only works if there the prime numbers smaller than n are stored in the array prime[] of nrPrime elements.
You can use this function to generate them:
http://snippets.dzone.com/posts/show/4189
This only works if there the prime numbers smaller than n are stored in the array prime[] of nrPrime elements.
You can use this function to generate them:
http://snippets.dzone.com/posts/show/4189
1 2 int phi(int n) { 3 double rez = n; 4 5 int i = 0; 6 while ((i < nrPrime) && (prime[i] <= n)) { 7 if (n % prime[i] == 0) { 8 rez *= (double)(prime[i] - 1) / (double)prime[i]; 9 } 10 ++i; 11 } 12 13 return rez; 14 }
