JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Prime Numbers, Factorization and Euler Function (Article) Euler function
 Re: Euler function (response to post by stubbscroll) | Reply thanks for explaining :)
 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.
 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 ?
 Forums Tutorial Discussions Prime Numbers, Factorization and Euler Function (Article) Euler function Previous Thread  |  Next Thread