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.
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.