Euler 's Totient Function | Python 3 program to calculate Euler ' s ▁ Totient ▁ Function ▁ using ▁ Euler ' s product formula ; Consider all prime factors of n and for every prime factor p , multiply result with ( 1 - 1 / p ) ; Check if p is a prime factor . ; If yes , then update n and result ; If n has a prime factor greater than sqrt ( n ) ( There can be at - most one such prime factor ) ; Driver program to test above function
def phi ( n ) : NEW_LINE INDENT p = 2 NEW_LINE while p * p <= n : NEW_LINE INDENT if n % p == 0 : NEW_LINE INDENT while n % p == 0 : NEW_LINE INDENT n = n // p NEW_LINE DEDENT result = result * ( 1.0 - ( 1.0 / float ( p ) ) ) NEW_LINE DEDENT p = p + 1 NEW_LINE DEDENT if n > 1 : NEW_LINE INDENT result = result * ( 1.0 - ( 1.0 / float ( n ) ) ) NEW_LINE DEDENT return int ( result ) NEW_LINE DEDENT for n in range ( 1 , 11 ) : NEW_LINE INDENT print ( " phi ( " , n , " ) ▁ = ▁ " , phi ( n ) ) NEW_LINE DEDENT