Solution Description: | Basically, for a given integer n, we want to know how many numbers < n are co-prime with n. Luckily, there's a function that does exactly that: Euler's totient (phi) function.
phi(n) = n * [(1 - 1/p) for all primes p such that p|n]
So, factor n, and use the prime factors to computer phi(n). |