Calculation of euler phi function

Question

int phi (int n) {
    int result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

I saw the above implementation of Euler phi function which is of the O(sqrt n).I don't get the fact of using i*i<=n in the for loop and need of changing n.It is said that it can be done in a time much smaller O (sqrt n) How? link (in Russian)

Answer 1

i*i<=n is same as i<= sqrt(n) from which your iteration lasts only to order of sqrt(n).

Using the straight definition of Euler totient function you are supposed to find the prime numbers that divides n.