ETF - Euler Totient Function
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <math.h>
main()
{
long n[200],t=2,T,N;
n[1]=2;
n[2]=3;
for(long i=4;i<1100;i++)
{
int k=0;
for(long j=1;j<=t;j++)
{
if(i%n[j]==0)
{
k=1;
break;
}
else if(n[j]>sqrt(i))
break;
}
if(k==0)
{
t++;
n[t]=i;
}
}
scanf("%ld",&T);
for(int i=1;i<=T;i++)
{
scanf("%ld",&N);
long k=1,KQ=1;
for(long i=1;i<=180;i++)
{
if(N==1)
break;
else if(n[i]>sqrt(N))
{
KQ*=(N-1);
break;
}
else if(N%n[i]==0)
{
long t=0;
do
{
N=N/n[i];
t++;
}while(N%n[i]==0);
KQ=KQ*(n[i]-1)*pow(n[i],t-1);
}
}
printf("%ld\n",KQ);
}
//getch();
}