1

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.

prostak
  • 139
  • 6
  • Perhaps investigate by printing `i` when `n%i` is 0? You'll find that the for loop finds the prime factors of `n` (except maybe for the last one), and `result` is the product n(1-1/p1)*(1-1/p2)... where the p's are the primes found so far. – Paul Hankin Feb 23 '22 at 21:23
  • Well, does it print the correct answer? It looks wrong to me. – President James K. Polk Feb 23 '22 at 21:56
  • @PresidentJamesK.Polk it is right – prostak Feb 23 '22 at 22:00
  • @PaulHankin but how result can be the product if we always decreasing it? – prostak Feb 23 '22 at 22:01
  • Ok, I think I see how it works. If n=(p1\*\*k1) * (p2\*\*k2) * ... then `result` starts out as n, and as each prime is p is found the factor p\*\*k is replaced in result by (p\*\*k - p\*\*(k-1)). Try it by hand with n as the product of two primes. – President James K. Polk Feb 23 '22 at 22:18
  • Probably `i <= n / i` is a better termination condition for the loop to avoid int overflow in more cases – Paul Hankin Feb 24 '22 at 07:48

2 Answers2

4

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.

Alexandru Borza
  • 136
  • 5
  • but how result can be product of `n*(1-1/p1)...(1-1/pk)` if we always decreasing it? – prostak Feb 23 '22 at 22:05
  • @prostak Because `n*(1-1/p1)` is `n - n/p1`. So you subtract `n/p1` from `n` to get a smaller `n`. Then repeat for the next prime factor. – user3386109 Feb 23 '22 at 22:40
3

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.

rici
  • 234,347
  • 28
  • 237
  • 341