Sieving For Totients
July 10, 2012
The totient of a number n is the count of the numbers less than n that are coprime to it; two numbers are coprime if they have no common factor other than 1. For instance, the totient of 30 is 8, since the numbers 1, 7, 11, 13, 17, 19, 23 and 29 are coprime to 30. The totient function was discovered by Leonhard Euler, and it pops up in all kinds of strange places in number theory; for instance, the totatives of 30 are the spokes on a 2,3,5 factorization wheel. We have seen the totient function in a previous exercise.
If you want to know the totient of a single number m, the best way to find it is to factor n and take the product of 1 less than each factor; for instance, 30 = 2 * 3 * 5, and subtracting 1 from each factor, then multiplying, gives the totient 1 * 2 * 4 = 8. But if you want to find the totients of all the numbers less than a given n, a better approach than factoring each of them is sieving. The idea is simple: Set up an array X from 0 to n, store i in each Xi, then run through the array starting from 0 and whenever Xi = i loop over the multiples of i, multiplying each by i − 1.
Your task is to write a function that computes all the totients less than n by sieving. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 