Time Limit Exceeded for ETF - Euler Totient Function at Spoj
The way I would approach this problem is to find the prime factorization of n, and then use Euler's formula which says:

$$\varphi(n) = n \prod_{p|n}\left(1 - \frac{1}{p}\right)$$

The easiest way to do this is to find the prime factorization of n (which you are basically already doing), but store each distinct prime factor in a list. Once you are done, compute this formula for the primes, and you should have your answer fairly quickly.