题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1286
欧拉函数：对正整数n，欧拉函数是求少于n的数中与n互质的数的数目；
素数（质数）指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数.
int Euler(int n)///返回n以内与n互质的数的个数；
{
int ret=1;
for(int i=2; i*i<=n; i++)
{
if(n%i==0)
{
n/=i;
ret*=i-1;
while(n%i==0)
{
n/=i;
ret*=i;
}
}
}
if(n>1)
ret*=n-1;
return ret;
}
筛选法求n以内所有的欧拉函数值（ O(n) ）
/*线性筛O(n)时间复杂度内筛出N内欧拉函数值*/
int m[N], el[N], p[N], pcnt=0;//m[i]是i的最小素因数，p是素数，pt是素数个数
void make()
{
el[1]=1;
int k;
for(int i=2; i<N; i++)
{
if(!m[i])//i是素数；
{
p[pcnt++]=m[i]=i;
el[i]=i-1;
}
for(int j=0; j<pcnt&&(k=p[j]*i)<N; j++)
{
m[k]=p[j];
if(m[i]==p[j])//为了保证以后的数不被再筛，要break
{
el[k]=el[i]*p[j];//这里的el[k]与el[i]后面的∏(p[i]-1)/p[i]都一样（m[i]==p[j]）只差一个p[j]，就可以保证∏(p[i]-1)/p[i]前面也一样了；
break;
}
else
el[k]=el[i]*(p[j]-1);//积性函数性质，f(i*k)=f(i)*f(k)；
}
}
}
#include<stdio.h> int Euler(int n)///返回n以内与n互质的数的个数； { int ret=1; for(int i=2; i*i<=n; i++) { if(n%i==0) { n/=i; ret*=i-1; while(n%i==0) { n/=i; ret*=i; } } } if(n>1) ret*=n-1; return ret; } int main() { int T, n; scanf("%d", &T); while(T--) { scanf("%d", &n); printf("%d\n", Euler(n)); } return 0; }
原文：http://www.cnblogs.com/zhengguiping--9876/p/4988679.html
