Can someone explain me, what is mean this Euler function:

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 tried to make a standart path to solve this task, but it is over time limit. I found this interpretation of Euler function, but I can't understand it. Why we're iterating i*i<n not i<n, what's happening in while loop and so on. I know that we can write Euler function as f(n) = n * (1-1/p1)(1-1/p2)...(1-1/pk), where pi is a prime number, but I don't understand how this code is working.

CodePudding user response：

We are iterating like this for the time performance because all prime factors of a number are equal or less with the square root of that number (if a number has not on of this, then it is a prime number). Then when we find a prime factor of the number we divide our number n by that factor until we can no longer divide it so we are extracting the prime factor from the number.

CodePudding user response：

r*(1-1/pk) = r - r/pk

Which is precisely what result -= result/i does. result is the product up to this point and i is the next prime divisor.