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;

Related Posts