欧拉函数打表
#include "stdio.h"
#define n 3000001
__int64 phi[n]; //不能用int
void getphi(){
for(int i=2;i<n;i++)phi[i]=0;
phi[1]=1;
for(int i=2;i<n;i++)
if(!phi[i])
for(int j=i;j<n;j+=i)
{
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
int main(){
int a,b;
getphi();
while(scanf("%d%d",&a,&b)!=EOF){
__int64 sum=0;
for(int i=a;i<=b;i++){
sum+=phi[i];
}
printf("%I64d\n",sum);
}
return 0;
}
原文:http://www.cnblogs.com/Mr-Xu-JH/p/3862663.html