ACM-欧拉筛

线性筛，复杂度为O(n)。与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式，通过最小质因数来判断当前合数是否已经被标记过。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=10000;     / / 从2->maxn范围内质数
int prime[MAXN],pnum=0;   / /prime[i] 第i个质数   pnum通过++操作可知道一共多少个某个范围内质数的数量
bool p[MAXN]={false};     / /某个数是否为质数 

void eulerSieve(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(p[i]==false){prime[++pnum]=i;}
        for(int j=1;j<=pnum;j++)
        {
            if(i*prime[j]>n){break;}
            p[i*prime[j]]=true;
            if(i%prime[j]==0){break;}//看注1
        }
    }
}
           

注1：欧拉筛的难点就在于对if (i % prime[j] == 0)这步的理解，当i是prime[j]的整数倍时，记 m = i / prime[j]，那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]，这说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要再进行标记(在之后会被 prime[j] * 某个数 标记)，对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就避免了重复标记。