欧拉函数，要一次性求出所有的欧拉函数，不能用单求一个数的欧拉函数的板子，具体思路就是下打遍素数筛，判断哪些数是素数哪些不是，然后也用筛法来计算每个数的欧拉函数
首先先初始化phi(i)=i，对应欧拉函数phi(N)的那个因子N
然后我们要做的从2开始筛，找到一个素数的时候把他的所有倍数都*(i-1)/i；找到一个合数的时候就不用管他，最终就计算出来了，其实跟素数筛类似
AC代码：
#include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long LL; const int maxn=1e6+10; bool v[maxn];//合数标记 void find_primes(int n) { memset(v,false,sizeof(v)); for(int i=2;i<=n;i++){ if(v[i]) continue; //优化：从x^2开始,(x+1)*x...到N/x*x结束,标记为合数即可 for(int j=i;j<=n/i;j++) v[i*j]=true; } } LL phi[maxn]; LL db[maxn]; void init() { for(LL i=0;i<maxn;i++) phi[i]=i; for(LL i=2;i<maxn;i++){ if(v[i]) continue; for(LL j=i;j<maxn;j+=i){ phi[j]=phi[j]*(i-1)/i; } } for(LL i=2;i<maxn;i++) db[i]=db[i-1]+phi[i]; } int main() { find_primes(maxn-1); init(); LL n; while(~scanf("%lld",&n)){ if(!n) break; printf("%lld\n",db[n]); } }