The Euler function http://acm.hdu.edu.cn/showproblem.php?pid=2824

 1 #include<cstdio> 2 #include<cstring> 3 #define mt(a,b) memset(a,b,sizeof(a)) 4 typedef __int64 LL; 5 const int M=3000010; 6 int phi[M];//小于i并且与i互素的个数 7 int pri[M],pricnt; 8 void sieve_phi(){//筛法求欧拉函数phi 9     pricnt=0;10     mt(phi,0);11     phi[1]=1;12     for(int i=2;i<M;i++){13         if(!phi[i]){14             pri[pricnt++]=i;15             phi[i]=i-1;16         }17         for(int j=0;pri[j]*i<M;j++){18             if(i%pri[j]){19                 phi[i*pri[j]]=phi[i]*(pri[j]-1);20             }21             else{22                 phi[i*pri[j]]=phi[i]*pri[j];23                 break;24             }25         }26     }27 }28 int main() {29     sieve_phi();30     int x,y;31     while(~scanf("%d%d",&x,&y)){32         LL ans=0;33         for(int i=x;i<=y;i++){34             ans+=phi[i];35         }36         printf("%I64d\n",ans);37     }38     return 0;39 }

 1 #include<cstdio> 2 #include<cstring> 3 #define mt(a,b) memset(a,b,sizeof(a)) 4 typedef __int64 LL; 5 const int M=1000010; 6 int phi[M];//小于i并且与i互素的个数 7 int pri[M],pricnt; 8 void sieve_phi(){//筛法求欧拉函数phi 9     pricnt=0;10     mt(phi,0);11     phi[1]=1;12     for(int i=2;i<M;i++){13         if(!phi[i]){14             pri[pricnt++]=i;15             phi[i]=i-1;16         }17         for(int j=0;pri[j]*i<M;j++){18             if(i%pri[j]){19                 phi[i*pri[j]]=phi[i]*(pri[j]-1);20             }21             else{22                 phi[i*pri[j]]=phi[i]*pri[j];23                 break;24             }25         }26     }27 }28 LL sum[M];29 int main() {30     sieve_phi();31     sum[1]=0;32     for(int i=2;i<M;i++){33         sum[i]=sum[i-1]+phi[i];34     }35     int n;36     while(~scanf("%d",&n),n){37         printf("%I64d\n",sum[n]);38     }39     return 0;40 }