线性筛(欧拉筛)_欧拉筛的常数

欧拉筛

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34