Number of coprimes of n
15 Oct 2017
Two numbers a and b are co-primes, if the GCD(Greatest Common Divisor) between a and b is 1.
Euler's Totient(n) is count of co-primes/relatively primes less than or equal to given n.
A naive solution to find Euler's Totient, is by iterating through i from 1 to n-1 and finding count of numbers that have GCD(i, n) as 1. This solution has complexity of O(n). There is another efficient algorithm that reduces complexity further.
int phi(int n)
{
int result = n;
for (int p=2; p*p<=n; ++p)
{
// Check if p is a prime factor.
if (n % p == 0)
{
// Divide it until, we remove all multiple of current p
while (n % p == 0)
n /= p;
result -= result / p;
}
}
// For cases where a prime factor of n is greater than SQRT(n)
if (n > 1)
result -= result / n;
return result;
}
int main()
{
int n;
for (n=1; n<=10; n++)
printf("phi(%d) = %d\n", n, phi(n));
return 0;
}