Euler Totient Function (Sieve and Brute force)

By | August 26, 2015

Euler’s Totient Function (Sieve and Brute force).

In number theory, Euler’s totient function (or Euler’s phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n.
(These integers are sometimes referred to as totatives of n.)
Thus, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ kn for which the greatest common divisor gcd(n, k) = 1.

It states that

 \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),

where the product is over the distinct prime numbers dividing n.

To know about all the other properties, click Here.

Example:

Input: 25
Answer:  20

Input: 2
Answer: 1

There are two implementations for finding Euler Totient Function.

Approach 1. Brute Force

Here is the working code:

int phi(int n)
{
     int result=n;
     for(int i=2;i*i<=n;++i)
          if(n%i==0)
          {
               while(n%i==0)
                    n/=i;
               result-=result/i;
          }
     
          if(n>1)
               result-=result/n;
     return result;
}

Time Complexity: O(n1/2)

Output:

1
20

Approach 2. Totient Sieve

Here is the working code:

int tot[size+1]; //global
unsigned long long arr[size+1];

void euler_tot() { //Seive to build the array that stores totient values
    tot[1] = 1;
    for(int i=2; i<size; i++) 
    {
        if(!tot[i]) 
        {
            tot[i] = i-1;
            for(int j=(i<<1); j<=size; j+=i) 
            {
                if(!tot[j]) tot[j] = j;
                tot[j] = tot[j]/i*(i-1);
            }
        }
    }
}