Time Limit Exceeded for ETF - Euler Totient Function at Spoj In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 ≤ n ≤ 106), compute the value of the totient φ.

For the code written below, this is giving TLE. How i can optimize this code or should i prefer some other language for this problem.
Link of the problem at spoj

test = int(input())
for t in range(test):
    n = int(input())
    result = n
    i = 2
    while i*i &lt;= n :
        if n %i == 0:
            while n%i == 0 :
                n /= i
            result -=result/i
        i +=1
    if n &gt; 1:
        result -= result/n
    print(int(result))
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.