**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.

Denition 1.1. Let n 1 be an integer. Then we dene 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; } |