Optimized Euler Totient Function for Multiple Evaluations | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE const int MAX = 100001 ; vector < ll > p ; void sieve ( ) { ll isPrime [ MAX + 1 ] ; for ( ll i = 2 ; i <= MAX ; i ++ ) { if ( isPrime [ i ] == 0 ) { p . push_back ( i ) ; for ( ll j = 2 ; i * j <= MAX ; j ++ ) isPrime [ i * j ] = 1 ; } } } ll phi ( ll n ) { ll res = n ; for ( ll i = 0 ; p [ i ] * p [ i ] <= n ; i ++ ) { if ( n % p [ i ] == 0 ) { res -= ( res / p [ i ] ) ; while ( n % p [ i ] == 0 ) n /= p [ i ] ; } } if ( n > 1 ) res -= ( res / n ) ; return res ; } int main ( ) { sieve ( ) ; cout << phi ( 11 ) << " STRNEWLINE " ; cout << phi ( 21 ) << " STRNEWLINE " ; cout << phi ( 31 ) << " STRNEWLINE " ; cout << phi ( 41 ) << " STRNEWLINE " ; cout << phi ( 51 ) << " STRNEWLINE " ; cout << phi ( 61 ) << " STRNEWLINE " ; cout << phi ( 91 ) << " STRNEWLINE " ; cout << phi ( 101 ) << " STRNEWLINE " ; return 0 ; }