DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world
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
int phi(int n) {
double rez = n;
int i = 0;
while ((i < nrPrime) && (prime[i] <= n)) {
if (n % prime[i] == 0) {
rez *= (double)(prime[i] - 1) / (double)prime[i];
}
++i;
}
return rez;
}
