Euler function (Phi) Problem
How to Solve:
if n is prime then number of relative prime from 1 upto n is n-1.
This is represented as phi function.
if n and m relatively prime then phi(mn)=phi(n)*phi(m). (proof given bellow as matrix representation of the 1 from mn)
The problem was solved by taking the number of relatively prime numbers as n.
Then dividing by the prime numbers (if divisible) n and subtracting the numbre of divisible numbers from result. (this removes all
the conjugated numbers from n)
Finally if there is any prime numbers left(that was checked in line if(n>1))
the divisible numbers were subtracted from result.
Related Theory:
1 The Euler Phi Function
This lecture is dedicated to the study of another multiplicative functions, the Euler phi
function.
De nition 1.1. Let n 1 be an integer. Then we de ne the Euler phi function by
(n) =the number of positive integers less than n that are relatively prime to n.
So let us do some examples.
Example 1.2. (1) = 1; (2) = 1; (3) = 2; (4) = 2; (5) = 4; (6) = 2; (15) = 8
The rst observation is how (n) behaves on the primes.
Observation 1. (n) = n
Proof. (n) = n
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> using namespace std; #define LL long long int LL phi(LL n) { LL r=n; if(n==1) return 1; if(n%2==0) { r-=r/2; while(n%2==0) n/=2; } for(LL j=3;j*j<=n;j+=2) { if(n%j==0) r-=r/j; while(n%j==0) n/=j; } if(n>1) r-=r/n; return r; } int main() { LL n; while(cin>>n) { if(n==0) break; cout<<phi(n)<<"\n"; } return 0; } |