int prime[MAXN]; //保存质数 int vis[MAXN]; //记录是否被筛 int euler_sieve(int n){ //欧拉筛。返回质数的个数。 int cnt = 0; //记录质数个数 memset(vis,0,sizeof(vis)); memset(prime,0,sizeof(prime)); for(int i=2;i<=n;i++){ //检查每个数,筛去其中的合数 if(!vis[i]) prime[cnt++]=i; //如果没有筛过,是质数,记录。第一个质数是2 for(int j=0; jn) break; //只筛小于等于n的数 vis[i*prime[j]]=1; //关键1。用x的最小质因数筛去x if(i%prime[j]==0) break; //关键2。如果不是这个数的最小质因子,结束 } } return cnt; //返回小于等于n的素数的个数 }