int fi(int n)
{
int result = n;
for(int i=2;i*i <= n;i++)
{
if (n i == 0) result -= result / i;
while (n i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
This code here int the for() loop does n*(1-1/P)… till the square root… I am unable to understand that when it comes out of the for loop we check if n>1 … Now if n>1 how are we sure that n is a prime number…
I visualise this as result*(1-1/P)…=(result-result/Prime)*(1-1/P2)…
Every composite number can be expressed as the product of two or more primes. So, when we have divided the number by all its possible factors, it gets reduced to the smallest possible prime. EX: if n=28,
28= 2^2 * 7;
We first get 2 as the factor, the while loop inside does the job of power here, i.e. divides 28 by 2^2, then we get n=7. The loop continues till sqrt(28) nearly 5, thus we don’t get 7 as its factor, see now that th eleft out n i.e. 7 is the prime.
Hope it clears… 