链接：点击打开链接
以前比赛看到过的一道题，以为是规律题，没做出来。然后学了欧拉函数，一看到这题，就知道思路，把10^6打一个表出来。prime[i]=prime[i-1]+phi[i]。其实大哥表就知道规律啦。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1000010
__int64 phi[maxn],prime[maxn];
int main(){
int i,j,n;
for (i = 1; i <= maxn; i++) phi[i] = i;
for (i = 2; i <= maxn; i += 2) phi[i] /= 2;
for (i = 3; i <= maxn; i += 2) if(phi[i] == i) {
for (j = i; j <= maxn; j += i)
phi[j] = phi[j] / i * (i - 1);
prime[2]=1;
}
for(i=3;i<=maxn;i++)
prime[i]=prime[i-1]+phi[i];
while(~scanf("%d",&n)){
if(n==0)
break;
printf("%I64d\n",prime[n]);
}
return 0;
}