线性筛(欧拉筛)

算法

用途：线性的求区间[1,n]的所有质数

Published

December 2, 2021

Content note — Needs verification · 待核验

线性筛证明中的“最小因数/最小质因数”表述和部分变量关系写错。

“i 一定是 p_j 的因数”应重新核对，语义上应是 p_j 整除 i。
代码使用 MAXN = 1e8+7 会带来非常高的静态内存占用，需结合题目内存限制验证。

线性筛(欧拉筛)

1.关于欧拉筛

用途：线性的求区间[1,n]的所有质数

事实上，优化以后的埃氏筛已经很优秀了，一般情况下，很难通过时间复杂度区分欧拉筛和埃氏筛。

所以我们为什么需要欧拉筛

欧拉筛可以完成很多计数，比如欧拉函数
欧拉筛比较高级且常数略小一些

2.原理和过程

过程：

欧拉筛的主要思想是，用已知的质数筛掉这个质数的倍数。且需要保证对于任意一个合数，它会且只会它的最小因数筛掉

所以我们只需要枚举i = 2~n（主意1不是质数)在这个过程中维护已经发现的所有质数的集合。然后筛掉这些质数的i倍。一旦发现某个质数\(p_j\)是i的因数，则不去筛所有比 \(p_j\)大的质数的i倍即：

if(!(i%prime[j]))break;

正确性证明：

\(\forall p_j 如果 i\)%\(p_j = 0\) , 那么:

1.\(p_j\)一定是i的最小质因数。因为\(p_j\)是质数且，如果i还有比\(p_i\)更小的因子，由于p数组是有序的，所以会在更靠前的位置被枚举到。为了满足对于任意一个合数，它会且只会它的最小因数筛掉，所以小于等于\(p_i\)的质数都可以被使用。

2. i 一定是\(p_j\)的因数。对于所有大于\(p_j\)的质数，很显然\(p_j\)不是\(p_j\times i\)的最小的因子，因为i里面一定有比\(p_i\)更小的因子。为了满足对于任意一个合数，它会且只会它的最小因数筛掉，所以不使用所有大于等于\(p_j\)的质数。

3.代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e8+7;
bool isprime[MAXN];
int prime[MAXN];
template <typename _TP>
inline _TP read(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
    X=w?-X:X;
    return X;
}
int main(){
    int n,x,t;
    read(n);read(t);
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    int cnt=0;
    for(int i=2;i<=n;i++){
        if(isprime[i])prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=false;
            if(!(i%prime[j]))break;
        }
    }
    for(int i=1;i<=t;i++){
        read(x);
        cout<<prime[x]<<'\n';
    }
    return 0;
}