Optimized Euler Totient Function for Multiple Evaluations | PHP 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
< ? php $ MAX = 100001 ; $ p = array ( ) ; function sieve ( ) { global $ MAX , $ p ; $ isPrime = array_fill ( 0 , $ MAX + 1 , 0 ) ; for ( $ i = 2 ; $ i <= $ MAX ; $ i ++ ) { if ( $ isPrime [ $ i ] == 0 ) { array_push ( $ p , $ i ) ; for ( $ j = 2 ; $ i * $ j <= $ MAX ; $ j ++ ) $ isPrime [ $ i * $ j ] = 1 ; } } } function phi ( $ n ) { global $ p ; $ res = $ n ; for ( $ i = 0 ; $ p [ $ i ] * $ p [ $ i ] <= $ n ; $ i ++ ) { if ( $ n % $ p [ $ i ] == 0 ) { $ res -= ( int ) ( $ res / $ p [ $ i ] ) ; while ( $ n % $ p [ $ i ] == 0 ) $ n = ( int ) ( $ n / $ p [ $ i ] ) ; } } if ( $ n > 1 ) $ res -= ( int ) ( $ res / $ n ) ; return $ res ; } sieve ( ) ; print ( phi ( 11 ) . " STRNEWLINE " ) ; print ( phi ( 21 ) . " STRNEWLINE " ) ; print ( phi ( 31 ) . " STRNEWLINE " ) ; print ( phi ( 41 ) . " STRNEWLINE " ) ; print ( phi ( 51 ) . " STRNEWLINE " ) ; print ( phi ( 61 ) . " STRNEWLINE " ) ; print ( phi ( 91 ) . " STRNEWLINE " ) ; print ( phi ( 101 ) . " STRNEWLINE " ) ; ? >