# 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 ≤ *k* ≤ *n* for which the greatest common divisor gcd(*n*, *k*) = 1.

It states that

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(n^{1/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); } } } }