Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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<int> 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<int>::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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

commented Jan 14, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.