线性筛(欧拉筛)
1.关于欧拉筛
用途：线性的求区间[1,n]的所有质数
事实上，优化以后的埃氏筛已经很优秀了，一般情况下，很难通过时间复杂度区分欧拉筛和埃氏筛。
所以我们为什么需要欧拉筛
- 欧拉筛可以完成很多计数，比如欧拉函数
- 欧拉筛比较高级且常数略小一些
2.原理和过程
过程：
欧拉筛的主要思想是，用已知的质数筛掉这个质数的倍数。且需要保证对于任意一个合数，它会且只会它的最小因数筛掉
所以我们只需要枚举i = 2~n（主意1不是质数)在这个过程中维护已经发现的所有质数的集合。然后筛掉这些质数的i倍。一旦发现某个质数$p_j$是i的因数，则不去筛所有比 $p_j$大的质数的i倍 即：
正确性证明：
$\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.代码
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
| #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;
}
|
