Euler function

Euler function

   Euler function is often called a function phi(n) shows the number of integers between 1 and n which are coprime with n. 

E(1)=1;

E(2)=2;

E(3)=3;

...

...

...

The Euler function can be calculated with prim factorization but here are some tips on calculating it faster.

1. If p is prime than E(p) = p-1 because every prime number is coprime with every number except itself.

2. If p is prime and a is an nteger than E(p^a) =p^a_ p^a-1   

3. If a and b are coprimes then E(a*b)=E(a)*E(b)

If  n=p1^a1*p2^a2*p3^a3*....*pn^an = (p1^a1-p1^(a1-1) ) * (p2^a2-p2^(a2-1)) * (pn^an - pn^(an-1)) = n * (1-1/p1) * (1-1/p2) * (1-1/p3) * ....* (1-1/pn)

Here is the function in C++ for calculating euler function

int phi (int n)
{
   int ans=n;
   for (int i=2; i*i<=n; ++i)
   if(n%i==0)
   {
while(n%i==0)
    n=n/i;
     ans=ans-ans/i;
   }
   if(n>1)
ans=ans-ans/n;
 return ans;
}