Instantly share code, notes, and snippets. cslarsen/euler_phi.cpp Created Jan 18, 2012

Euler's totient function phi --- a fast implementation in C++
 /* * Euler's totient function phi(n). * http://en.wikipedia.org/wiki/Euler%27s_totient_function * * This is an *EXTREMELY* fast function and uses * several tricks to recurse. * * It assumes you have a list of primes and a fast * isprime() function. Typically, you use a bitset * to implement the sieve of Eratosthenes and use * isprime() on that. You should also have a vector * of all known primes below a certain limit. * * Additionally, you should have a fast gcd algorithm. * * So, we have three dependencies here: * * - isprime(int) (typically look up bitset sieve) * - std::vector primes (vector of prime numbers, typically sieved) * - binary_gcd(int, int) or similar, fast, gcd function. * * This function is placed in the public domain by the author, * Christian Stigen Larsen, http://csl.sublevel3.org * */ int phi(const int n) { // Base case if ( n < 2 ) return 0; // Lehmer's conjecture if ( isprime(n) ) return n-1; // Even number? if ( n & 1 == 0 ) { int m = n >> 1; return !(m & 1) ? phi(m)<<1 : phi(m); } // For all primes ... for ( std::vector::iterator p = primes.begin(); p != primes.end() && *p <= n; ++p ) { int m = *p; if ( n % m ) continue; // phi is multiplicative int o = n/m; int d = binary_gcd(m, o); return d==1? phi(m)*phi(o) : phi(m)*phi(o)*d/phi(d); } }

vlad-shatskyi commented Aug 9, 2012

 In line 37 there must be (n & 1) == 0 because & has lower precedence then ==, as my compiler noticed. But condition n & 0 tests for evenness equally good.

jrraymond commented Jan 14, 2016

 According to https://en.wikipedia.org/wiki/Euler%27s_totient_function, phi(1)=1
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.