Skip to content

Instantly share code, notes, and snippets.

View andr1972's full-sized avatar

Andrzej Borucki andr1972

View GitHub Profile
@cslarsen
cslarsen / euler_phi.cpp
Created January 18, 2012 20:16
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