'Euler function in C++

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.

c++algorithmfunctionnumber-theoryeulers-number


Solution 1:[1]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 rici

Related Questions