这题用欧拉函数会超时，要用函数筛。
定义：对于正整数n，φ(n)是小于或等于n的正整数中，与n互质的数的数目。
例如：φ(8)=4，因为1，3，5，7均和8互质。
性质：1.若p是质数，φ(p)= p-1.
2.若n是质数p的k次幂，φ(n)=(p-1)*p^(k-1)。因为除了p的倍数都与n互质
3.欧拉函数是积性函数，若m,n互质，φ(mn)= φ(m)φ(n).
根据这3条性质我们就可以推出一个整数的欧拉函数的公式。因为一个数总可以写成一些质数的乘积的形式。
E(k)=(p1-1)(p2-1)...(pi-1)*(p1^(a1-1))(p2^(a2-1))...(pi^(ai-1))
= k*(p1-1)(p2-1)...(pi-1)/(p1*p2*...*pi)
= k*(1-1/p1)*(1-1/p2)...(1-1/pk)
在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值（a为N的质因素）
若( N%a ==0&&(N/a)%a ==0)则有：E(N)= E(N/a)*a;
若( N%a ==0&&(N/a)%a !=0)则有：E(N)= E(N/a)*(a-1);
Description
Input
Output
Sample Input
Sample Output
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 using namespace std; 7 #define INF 3000005 8 int target[INF],phi[INF]; 9 bool pri[INF]; 10 void prime()//欧拉数筛 11 { 12 int i,j=0,cot=0; 13 for(i=2;i<INF;i++)//循环每个数 14 { 15 if(pri[i]==false)//当前这个数是置否的 16 { 17 target[cot++]=i;//加入素数数组 18 phi[i]=i-1;//将质数加入欧拉函数数组，因为没有其他的数是他的因子了，所以他的欧拉函数就是i-1 19 } 20 for(j=0;j<cot&&i*target[j]<INF;j++)//循环质数 21 { 22 pri[i*target[j]]=true;//所有质数乘以当前倍数的值置真 23 if(i%target[j]==0)//循环判断当前这个数i的质因子有哪些，一次计算一个乘法 24 phi[i*target[j]]=phi[i]*target[j]; 25 else 26 phi[i*target[j]]=phi[i]*(target[j]-1);//结束的时候乘以质数减一 27 } 28 } 29 } 30 int main() 31 { 32 int i,j,m,n,a,b; 33 long long sum; 34 prime(); 35 while(scanf("%d%d",&a,&b)!=EOF) 36 { 37 sum=0; 38 for(i=a;i<=b;i++) 39 sum+=phi[i]; 40 printf("%lld\n",sum); 41 } 42 return 0; 43 }
原文：http://www.cnblogs.com/linminxuan/p/4395744.html