Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Euler function | Reply
The function fi(n) finds the value of φ(n):

      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; 

Could someone please tell whether " if(n > 1)" condition would hold true only when n is prime ?
Re: Euler function (response to post by erudite) | Reply
No, it occurs more often than that. It happens whenever the largest prime factor that divides n occurs once (that is, its square doesn't divide n). If the largest prime factor is a square or a higher power, n is divided all the way down to 1 in the loop. Otherwise, what remains of n is a prime larger than i*i.
Re: Euler function (response to post by stubbscroll) | Reply
thanks for explaining :)