Euler 's Totient function for all numbers smaller than or equal to n | Computes and prints totient of all numbers smaller than or equal to n . ; Create and initialize an array to store phi or totient values ; Compute other Phi values ; If phi [ p ] is not computed already , then number p is prime ; Phi of a prime number p is always equal to p - 1. ; Update phi values of all multiples of p ; Add contribution of p to its multiple i by multiplying with ( 1 - 1 / p ) ; Print precomputed phi values ; Driver code
def computeTotient ( n ) : NEW_LINE INDENT phi = [ ] NEW_LINE for i in range ( n + 2 ) : NEW_LINE INDENT phi . append ( 0 ) NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( phi [ p ] == p ) : NEW_LINE INDENT phi [ p ] = p - 1 NEW_LINE for i in range ( 2 * p , n + 1 , p ) : NEW_LINE INDENT phi [ i ] = ( phi [ i ] // p ) * ( p - 1 ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( " Totient ▁ of ▁ " , i , " ▁ is ▁ " , phi [ i ] ) NEW_LINE DEDENT DEDENT n = 12 NEW_LINE computeTotient ( n ) NEW_LINE