题解 P3383 【【模板】线性筛素数】

题意:「查找第 k 小的质数」。
这需要打表生成质数数组（prime[i]表示第 i 个质数）。

如下是一般的筛法(埃氏筛)：

//生成不大于 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 的数据，会超时。
所以，用这种方法提交，会爆零（我是这样的）。

那么，现在要避免重复筛，要用到另一种筛法：欧拉筛。
先上代码：

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筛一次）
以此类推，可做出一张表：

每个质数只被筛一次，复杂度变为 O(n) ，可以AC。

2020/02/01 写完。
2020/02/12 小小的修改。