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
#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;
}