Optimized Euler Totient Function for Multiple Evaluations | Java 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 ) ; Driver code ; preprocess all prime numbers upto 10 ^ 5
import java . util . * ; class GFG { static int MAX = 100001 ; static ArrayList < Integer > p = new ArrayList < Integer > ( ) ; static void sieve ( ) { int [ ] isPrime = new int [ MAX + 1 ] ; for ( int i = 2 ; i <= MAX ; i ++ ) { if ( isPrime [ i ] == 0 ) { p . add ( i ) ; for ( int j = 2 ; i * j <= MAX ; j ++ ) isPrime [ i * j ] = 1 ; } } } static int phi ( int n ) { int res = n ; for ( int i = 0 ; p . get ( i ) * p . get ( i ) <= n ; i ++ ) { if ( n % p . get ( i ) == 0 ) { res -= ( res / p . get ( i ) ) ; while ( n % p . get ( i ) == 0 ) n /= p . get ( i ) ; } } if ( n > 1 ) res -= ( res / n ) ; return res ; } public static void main ( String [ ] args ) { sieve ( ) ; System . out . println ( phi ( 11 ) ) ; System . out . println ( phi ( 21 ) ) ; System . out . println ( phi ( 31 ) ) ; System . out . println ( phi ( 41 ) ) ; System . out . println ( phi ( 51 ) ) ; System . out . println ( phi ( 61 ) ) ; System . out . println ( phi ( 91 ) ) ; System . out . println ( phi ( 101 ) ) ; } }