## Issue

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.

## Solution

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.

Answered By – Alexandru Borza

Answer Checked By – David Marino (BugsFixing Volunteer)