sympy/sympy — pull request #1086 by catchmrbharath (2012-02-26 12:43:45+00:00)
Title: A faster totient function

The old totient function was iterating over all numbers less than n and calculating whether the gcd is 1 which would take O{n*logn} time.

The new totient function iterates over the primes less than sqrt(n) (which is cached I think) and calculates the totient function. This will take O{sqrt(n)} time.