Brute-forcing Eurler #70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6....

First I was trying to  brute-force the solution using FT of Euler totient function (http://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform), than through the definition but all these solutions was too long to wait. In the end finished with product formula.

In the process of solution found quite faster recipe from ActiveState on generating prime numbers (http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/).

Also used multiprocessing module to speed up solution.

And after...

$ time ./70.py 
(8319823, 8313928, 1.0007090511248113)

real    235m23.873s
user    1644m0.217s
sys     0m36.206s