Explain the implementation of Euler's Totient Implementation

Refresh

March 2019

Views

9 time

2

I have seen this code in a coding platform to efficiently calculate the euler's totient for different values. I am not being able to understand this implementation. I really want to learn this. Could anyone please help me explain this?

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

0 answers