http://acm.hdu.edu.cn/showproblem.php?pid=1286
学到了筛法求欧拉函数。即欧拉函数φ(n)表示≤n且与n互素的正整数的数目（其实等于仅对1而言，φ(1)=1，1被认为与任何数互素）。
编程求一个数的φ(n)显然很简单，用gcd()就可以了，但如果求一个很大范围（N）内所有数的欧拉函数值，gcd()就难以胜任了。
在网上找了一下，发现欧拉函数的一个公式：
φ(n)=n*（1-1/p1)(1-1/p2)....(1-1/pk),其中p1、p2…pk为n的所有素因子。
比如：φ(12)=12*(1-1/2)(1-1/3)=4。
利用这个就比较好求了，可以用类似求素数的筛法。
先筛出N以内的所有素数，再以素数筛每个数的φ值。
比如求10以内所有数的φ值：
设一数组phi[11]，赋初值phi[1]=1,phi[2]=2...phi[10]=10；
然后从2开始循环，把2的倍数的φ值*(1-1/2)，则phi[2]=2*1/2=1,phi[4]=4*1/2=2,phi[6]=6*1/2=3....；
再是3，3的倍数的φ值*(1-1/3)，则phi[3]=3*2/3=2,phi[6]=3*2/3=2，phi[9]=.....；
再5，再7...因为对每个素数都进行如此操作，因此任何一个n都得到了φ(n)=n*（1-1/p1)(1-1/p2)....(1-1/pk)的运算
觉得这个“筛”还是比较好用的，以前求数的所有因子之和也是用的它。
#include<stdio.h> #include<string.h> int phi[33000]; int gphi() { int i,j; memset(phi,0,sizeof(phi)); phi[1]=1;//与1互质的只有他本身一个 for(i=2;i<33000;i++) if(!phi[i])//因为在计算中j是以i在叠加的，所以所有被叠加到的数都是合数，所以当i //依次增加到那个数的时候发现那个数已经被赋值，表明那是个合数，无须再算，所以这里如果已经被赋值过了，就不能再进行计算了 //反之如果没被赋值，说明这个数肯定不是之前数的倍数，也就是i是质数，可以进行下面phi的计算 for(j=i;j<33000;j+=i)//这里重要的筛法，j+=i，表示以下出现的数，i都是j的因子 { if(!phi[j])phi[j]=j;//未赋值的时候，要先赋值为其本身 phi[j]=phi[j]/i*(i-1);//phi[j]=phi[j]*(1-1/i)会出现错误，因为1/i都变成0了 } } int main() { int cn,n; gphi(); scanf("%d",&cn); while(cn--&&scanf("%d",&n)) printf("%d ",phi[n]); return 0; }