作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。
共一个数N。
共一个数，即C君应看到的学生人数。
【数据规模和约定】 对于 100% 的数据，1 ≤ N ≤ 40000
1 #include<cstdio> 2 const int maxn=40010; 3 bool pd[maxn]; 4 int phi[maxn],prime[maxn],top,n,ans; 5 void ES(){ 6 for(int i=2;i<n;i++){ 7 if (!pd[i]){ 8 prime[++top]=i; 9 phi[i]=i-1; 10 } 11 for (int j=1;j<=top&&prime[j]*i<=n;j++){ 12 pd[prime[j]*i]=1; 13 if (i%prime[j]==0){ 14 phi[prime[j]*i]=phi[i]*prime[j]; 15 break; 16 } 17 phi[prime[j]*i]=phi[i]*(prime[j]-1); 18 } 19 } 20 } 21 22 int main(){ 23 scanf("%d",&n); 24 ES(); 25 for(int i=1;i<n;i++) phi[i]+=phi[i-1]; 26 ans=phi[n-1]*2+3; 27 printf("%d",ans); 28 }
原文：http://www.cnblogs.com/wuminyan/p/5116148.html