# 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

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

Example:

Input: 25

Input: 2

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