线性筛的简单证明

原理

线性筛是一种可以在线性时间内将素数筛选出来的算法，其中的主要思想在于保证合数只会被它的最小质因数筛掉并且筛掉一次。

代码

下面是线性筛的算法CPP实现：

vector<int> generate_primes_linear_time(int n) {
    vector<int> lp(n + 1);
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && primes[j] <= lp[i] && i * primes[j] <= n; ++j)
            lp[i * primes[j]] = primes[j];
    }
    return primes;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

其中$lp[i]$保存了$i$的最小质因数，$primes$则是存储了从小到大的质数。

简单证明

所有的合数只会被筛掉一次

假设存在一个合数被筛掉了两次，即存在合数$C=i\ast p_i=p_j\ast j(p_i>p_j)$，那么就可以得出它被两个不同的质数$p_i,p_j$筛过两次，那么很容易得到$p_j|i$，并且有$p_i>p_j$，那么表明此时对于倍数$i$的时候，在枚举到质数$p_j$就会退出循环而不会枚举到$p_i$，因此假设不成立。可以保证所有的合数有且并被筛过一次。

下一个没有被筛掉的数字一定是素数

假设下一个没有被筛掉的数字为$x$，那么我们假设它不是素数，则有$x=p_x\ast q(p_x<x,q<x)$其中$p_x$是$x$的最小质因数，那么对于倍数$q$，在枚举素数的时候没有枚举到$p_x$，表明存在更加小的素数$p_y$使得$p_y|q$，因此也有$p_y|x$，所以$p_x$并不是$x$的最小质因数。假设不成立，所以$x$是素数。