题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1286
欧拉函数：对正整数n，欧拉函数是求少于n的数中与n互质的数的数目；
素数（质数）指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数.
φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。
φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值，这里函数φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
若n为质数则φ(n)=n-1。
单独求n的欧拉函数值：
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)；
}
}
}
简单的写法：
int eul[N];
void Euler(int n)///打表法求eul[i] (i<n)
{
for(int i=2; i<n; i++)
{
if(eul[i]) continue;
for(int j=i; j<n; j+=i)
{
if(!eul[j]) eul[j] = j;
eul[j] = eul[j] / i * (i-1);
}
}
}
附上本题代码：
#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 ", Euler(n)); } return 0; }