题解 P3383 【【模板】线性筛素数】
Lylighter_
2020-02-01 11:50:50
题意:「查找第 $k$ 小的质数」。
这需要~~打表~~生成质数数组（`prime[i]`表示第 $i$ 个质数）。
***
如下是一般的筛法(**埃氏筛**)：
```cpp
//生成不大于 n 的所有质数
bool numlist[100000001];
int prime[20000001], cnt;
void work(int n){
for(int i=2; i<=n; i++){
if(numlist[i]==false){
prime[++cnt] = i ;
for(int j=i; i*j<=n; j++)
numlist[i*j] = true;
}
}
return;
}
```
埃氏筛的思想是：要想得到 $n$ 以内的质数，就要把不大于 $\sqrt n$ 的质数的倍数全部剔除，剩下的就是质数。从 $2$ 开始，把 $2$ 的倍数（不包括本身）标记为合数，然后向后枚举，查到一个未标记为合数的，就把它的倍数（不包括本身）标记为合数。以此类推，查到 $n$ 为止。
有一个小优化，把 $t$ 的倍数标记为合数时，不是从 $2t$ 开始，而是从 $t^2$ 开始（因为小于 $t^2$ 的 $t$ 的倍数在枚举到 $t$ 前就被标记过了）。
当然，埃氏筛效率还是低了些。例如一个数 $24$，它会被 $2$, $3$, $4$ 三个数标记，这就重复了两次，更大的数同理。时间复杂度 $O(n\log\log n)$，对于 $10^8$ 的数据，会超时。
所以，用这种方法提交，会爆零（我是这样的）。
***
那么，现在要避免重复筛，要用到另一种筛法：**欧拉筛**。
先上代码：
```cpp
bool numlist[100000001];
int prime[20000001], cnt;
void work(int n){
for(int i=2; i<=n; i++){
if(numlist[i]==false)
prime[++cnt] = i ;
for(int j=1; j<=cnt&&i*prime[j]<=n; j++){
numlist[i*prime[j]] = true ;
if(i%prime[j]==0)
break;
}
}
return;
}
```
避免重复筛，应找到筛合数的一种原则：这个合数只会被它的**最大非自身因数**（对应最小质因数）筛。这样能保证每个合数只会被筛一次。
（*运行过程*）从 $2$ 开始，$2$ 加入 prime 数组，再从小到大枚举质数（现在只有 $2$），筛掉质数与 $2$ 的乘积（$4$ 被筛掉）。
到了 $3$，$3$ 加入 prime 数组，从小到大枚举质数（此时有 $2$,$3$），筛掉质数与 $3$ 的乘积（$6$,$9$ 被筛掉）。
到了 $4$，$4$ 没加入 prime 数组，枚举质数（有$2$,$3$），筛掉 $8$ 后，因为 $4\bmod2=0$，触发退出条件。（不触发，就会筛掉 $12$，而 $12=2\times 2 \times 3$，又会被 $2$ 和 $6$筛一次）
以此类推，可做出一张表：
|$i$ 的值 |质数表 |筛去的数 |
| :----------- | :----------- | :----------- |
|2 |2 |4 |
|3 |2, 3 |6, 9 |
|4 |2, 3 |8 |
|5 |2, 3, 5 |10, 15, 25 |
|6 |2, 3, 5 |12 |
|7 |2, 3, 5, 7 |14, 21, 28, 35 |
|$\cdots$ |$\cdots$ |$\cdots$ |
每个质数只被筛一次，复杂度变为 $O(n)$ ，可以AC。
***
2020/02/01 写完。
2020/02/12 小小的修改。