N = p1 ^ K1 * p2 ^ k2 .................................. phi(N) = p1^(K1) * (1-1/p1) * .....................
phi(N) = N * (1 - 1/p1) * (1 - 1/p2) ..................................... phi(N) = (N - N/p1) * (1 - 1/p2).......................................... so now result which was initally N now is N - N / p1 phi(N) = result * (1 - 1/p2)........................... phi(N) = (result - result / p2) ............................... On Tue, Aug 30, 2011 at 6:27 PM, KK <[email protected]> wrote: > This is the code for the Euler phi 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; // M NOT GETTING THIS... > } > if (n > 1) > result -= result / n; > return result; > } > > why is it subtracting result/i from result if i is a factor of n?? > plzzz explain... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
