ETF - Euler Totient Function

                                     

ETF - Euler Totient Function

SPOJ: - http://www.spoj.com/problems/ETF/

CodeChef :- Rational Numbers (it is sum of phi upto n)

In number theory, Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.)

This is very common in number theory the formula for finding the number of numbers less than and co-prime with n is

N(1-1/p1)(1-1/p2).... where p1,p2.... refers to the distinct prime divisors of the number.

A example always makes it clear ,lets take n=20 hence the prime divisors are 2,5 hence by formula the number of numbers less than and prime to 20 should be 20*(1-1/2)(1-1/2)=20(1/2)(4/5)=8

Now we can count also

1,3,7,9,11,14,17,19

#include<bits/stdc++.h>

using namespace std;

int phi[1000005];

int main()

{

int i,j,k;

for(i=1;i<=1000000;i++)

    phi[i]=i;

for(i=2;i<=1000000;i++)

 if(phi[i]==i)

   for(j=i;j<=1000000;j+=i)

     phi[j]=(phi[j]/i)*(i-1);

int t;

cin>>t;

while(t--)

{

  int n;

  cin>>n;

  cout<<phi[n]<<endl;

}

return 0;

}