# Euler’s Totient Function

February 7, 2018Euler’s Totient function Φ(n) for an input n is count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

Examples:

Φ(1) = 1

gcd(1, 1) is 1

Φ(2) = 1

gcd(1, 2) is 1, but gcd(2, 2) is 2.

Φ(3) = 2

gcd(1, 3) is 1 and gcd(2, 3) is 1

Φ(4) = 2

gcd(1, 4) is 1 and gcd(3, 4) is 1

Φ(5) = 4

gcd(1, 5) is 1, gcd(2, 5) is 1,

gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2

gcd(1, 6) is 1 and gcd(5, 6) is 1,

Steps to be performed to get the result:

1) Initialize : result = n

2) Run a loop from ‘p’ = 2 to sqrt(n), do following for every ‘p’.

a) If p divides n, then

Set: result = result * (1.0 – (1.0 / (float) p));

Divide all occurrences of p in n.

3) Return result

**Find the below code in Python 3.0 to get the required Output:**

# Python 3 program to calculate

# Euler's Totient Function

# using Euler's product formula

def run(n) :

result = n # Initialize result as n

# Consider all prime factors

# of n and for every prime

# factor p, multiply result with (1 – 1/p)

p=2

while(p*p<=n) :

# Check if p is a prime factor.

if (n % p == 0) :

# If yes, then update n and result

while (n % p == 0) :

n = n // p

result = result * (1.0 – (1.0 / (float) (p)))

p = p + 1

# If n has a prime factor

# greater than sqrt(n)

# (There can be at-most one

# such prime factor)

if (n > 1) :

result = result * (1.0 – (1.0 / (float)(n)))

return (int)(result)

# Driver program to test above function

for n in range(1,11) :

print(“run(“,n,”) = “,run(n))