 # 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))```