Optimized Euler Totient Function for Multiple Evaluations | Python3 program to efficiently compute values of euler totient function for multiple inputs . ; Stores prime numbers upto MAX - 1 values ; Finds prime numbers upto MAX - 1 and stores them in vector p ; if prime [ i ] is not marked before ; fill vector for every newly encountered prime ; run this loop till square root of MAX , mark the index i * j as not prime ; function to find totient of n ; this loop runs sqrt ( n / ln ( n ) ) times ; subtract multiples of p [ i ] from r ; Remove all occurrences of p [ i ] in n ; when n has prime factor greater than sqrt ( n ) ; preprocess all prime numbers upto 10 ^ 5
MAX = 100001 ; NEW_LINE p = [ ] ; NEW_LINE def sieve ( ) : NEW_LINE INDENT isPrime = [ 0 ] * ( MAX + 1 ) ; NEW_LINE for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT if ( isPrime [ i ] == 0 ) : NEW_LINE INDENT p . append ( i ) ; NEW_LINE j = 2 ; NEW_LINE while ( i * j <= MAX ) : NEW_LINE INDENT isPrime [ i * j ] = 1 ; NEW_LINE j += 1 ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def phi ( n ) : NEW_LINE INDENT res = n ; NEW_LINE i = 0 ; NEW_LINE while ( p [ i ] * p [ i ] <= n ) : NEW_LINE INDENT if ( n % p [ i ] == 0 ) : NEW_LINE INDENT res -= int ( res / p [ i ] ) ; NEW_LINE while ( n % p [ i ] == 0 ) : NEW_LINE INDENT n = int ( n / p [ i ] ) ; NEW_LINE DEDENT DEDENT i += 1 ; NEW_LINE DEDENT if ( n > 1 ) : NEW_LINE INDENT res -= int ( res / n ) ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT sieve ( ) ; NEW_LINE print ( phi ( 11 ) ) ; NEW_LINE print ( phi ( 21 ) ) ; NEW_LINE print ( phi ( 31 ) ) ; NEW_LINE print ( phi ( 41 ) ) ; NEW_LINE print ( phi ( 51 ) ) ; NEW_LINE print ( phi ( 61 ) ) ; NEW_LINE print ( phi ( 91 ) ) ; NEW_LINE print ( phi ( 101 ) ) ; NEW_LINE