Number of coprimes of n

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;
}

Related Posts