Euler’s Totient Function using Python

Euler’s Totient function Φ(n) for an input n is count of numbers in the format of {1, 2, 3, 4, 5, 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))