线性筛

线性筛
术语名称	线性筛
英语名称	linear seive
别名	欧拉筛法, 欧拉筛, 线性筛法

线性筛法(linear seive)或线性筛，也称欧拉筛，是找出小于某正整数的全部质数的算法。这一算法是 Eratosthenes 筛法的改进版，因时间复杂度降低到线性复杂度而得名。

改进原理

理论上判定所有数的下限是遍历一次所有的数，而 Eratosthenes 筛法的时间复杂度为 [math]\displaystyle{ O(n\log n\log n) }[/math] ，可以考虑额外的复杂度是如何引入的。可以发现，过程中删去每个质数的全部倍数时，在有不同质因数的合数上执行了两次删除，这使得很多数字被重复删除多次（部分优化中，只执行平方以上的筛选，减少了部分重复，但是对商大于某个质因数的情况还会重复，比如 [math]\displaystyle{ 12 = 2\times 6 = 3\times 4 }[/math] ）。如果能保证每个数字只遍历一次，就可以得到线性复杂度的算法。

Euler 筛中在删除倍数的基础上进行了新的约束：每个数只被其最小质因数删除一次。

对任意一个数 [math]\displaystyle{ n = p_1^{n_1} p_2^{n_2} \cdots p_r^{n_r} }[/math] ，考虑在遍历其最小质因数 [math]\displaystyle{ p_1 }[/math] 时删除。但是对 [math]\displaystyle{ p_1 }[/math] 由于我们还没有找到 [math]\displaystyle{ p_2, \cdots, p_r }[/math] ，根本不知道哪些倍数是要删除的，只能调转一下思路。筛选时需要遍历所有整数，而不是所有质数。将其当作某个 [math]\displaystyle{ \tfrac{n}{p_1} = p_1^{n_1-1} p_2^{n_2} \cdots p_r^{n_r} }[/math] ，考虑所有可能的 [math]\displaystyle{ p_1 }[/math] 。注意这里存在 [math]\displaystyle{ n_1-1 =0 }[/math] 的情况，所以 [math]\displaystyle{ p_1 }[/math] 不一定是 [math]\displaystyle{ \tfrac{n}{p_1} }[/math] 的最小质因数，唯一能确认的是 [math]\displaystyle{ p_1 }[/math] 小于等于 [math]\displaystyle{ \tfrac{n}{p_1} }[/math] 的最小质因数。（因此流程上更像“每个数只被其与其最小质因数的商删除一次”，等价于被最小质因数删除了。）

因此需要额外记录每个数的最小质因数，用于判定其需要相乘的其他质数。显然由于每个数只被其最小质因数删除一次，在删除时记录下的最小质因数就是这里所需的最小质因数。

算法

列出所有正整数，删去 1 后，每次取出最前的数。

若这个数没有被删去，则自身是自身的最小质因数；若这个数被删去，则有最小质因数标记。删去其与全部小于等于其且未被删去的数的乘积。

直到所有的数都被遍历。

（规定范围时也可以遍历一半的数，因为之后的数乘以 2 不在筛选范围，不需要继续筛选）

举例

为了便于理解，这里将正整数 [math]\displaystyle{ n }[/math] 按照其质因数个数 [math]\displaystyle{ \Omega(n) }[/math] 分类：

[math]\displaystyle{ \Omega(1)=0 }[/math] ，即整数 1 ： 1 是被直接删去的。
[math]\displaystyle{ \Omega(p)=1 }[/math] ，即全体质数：不含有 1 和本身以外的因数，因此不会被其他因数删去。
[math]\displaystyle{ \Omega(p_1 p_2)=2 }[/math] ，即全体双质数：不妨设 [math]\displaystyle{ p_1 \leq p_2 }[/math] ，则遍历到 [math]\displaystyle{ p_2 }[/math] 时，遍历更小的质数 [math]\displaystyle{ 2,3,5,\cdots,p_1,\cdots,p_2 }[/math] 时，循环中会删去 [math]\displaystyle{ 2p_2,3p_2,5p_2,\cdots,p_1p_2,\cdots,p_2^2 }[/math] ，因此会正确删去这个数并标记其最小质因数为 [math]\displaystyle{ p_1 }[/math] 。
[math]\displaystyle{ \Omega(p_1 p_2 p_3)=3 }[/math] ：不妨设 [math]\displaystyle{ p_1 \leq p_2 \leq p_3 }[/math] ，则遍历到合数 [math]\displaystyle{ p_2 p_3 }[/math] 时，由于删去这个数时标记了其最小质因数为 [math]\displaystyle{ p_2 }[/math] ，那么会遍历更小的质数 [math]\displaystyle{ 2,3,5,\cdots,p_1,\cdots,p_2 }[/math] 时会删去 [math]\displaystyle{ 2p_2p_3,3p_2p_3,5p_2p_3,\cdots,p_1p_2p_3,\cdots,p_2^2p_3 }[/math] ，因此会正确删除这个数并标记其最小质因数为 [math]\displaystyle{ p_1 }[/math] 。
如果对任意 [math]\displaystyle{ \Omega(n)=r-1 }[/math] 的成立，考虑对 [math]\displaystyle{ \Omega(n)=r }[/math] ，设其最小质因数为 [math]\displaystyle{ p_1 }[/math] ，由于 [math]\displaystyle{ \Omega(\tfrac{n}{p_1})=r-1 }[/math] ，算法已经正确删去并标出其最小质因数 [math]\displaystyle{ p_2 \geq p_1 }[/math] ，因此对于[math]\displaystyle{ \tfrac{n}{p_1} }[/math] 将遍历并删去 [math]\displaystyle{ \tfrac{2n}{p_1},\tfrac{3n}{p_1},\tfrac{5n}{p_1},\cdots,\tfrac{p_1 n}{p_1}=n,\cdots,\tfrac{p_2 n}{p_1} }[/math] ，正确删去 [math]\displaystyle{ n }[/math] 并标记其最小质因数为 [math]\displaystyle{ p_1 }[/math] 。

因此根据第一数学归纳法，可以证明对于所有有自然数个质因子的数，即全体正整数，这一算法都能够正确筛选出其中的质数。

伪代码

过程 线性筛
别名 linear_seive
参数 n : 正整数 // 范围上限
返回 primes : 正整数的列表 // 质数列表

令 p₁~ₙ 为 未删去
令 f₁~ₙ 为 未初始化（使用 0 或 1 等不冲突的数值标记） // 最小质因数

循环 k
当 k ≤ n 时 ❶
执行
    如果 k 未删去 那么
        令 fₖ ← k
    将 k 加入列表 primes
    记 q ← 2 // 遍历更小的质数
    循环 q 当 q ≤ fₖ 时
        如果 q 已删去 那么
            继续下一循环
        记 n ← kq
        令 pₙ 为 已删去
        令 fₙ 为 q
    继续循环 q ← q + 1
继续循环 k ← k + 1

返回 primes

❶ 这里可以改为 2k ≤ n 。

复杂度

主要操作是遍历正整数及部分倍数，分为两部分。作为 k 遍历时，由于内层循环较为复杂，取决于标记情况，又知道所有合数都仅被标记一次，将其求和得到的是范围内全部合数，近似于范围内的全体正整数，即 [math]\displaystyle{ O(n) }[/math] 。

情况	复杂度估计	渐近级别	发生条件
平均情况	[math]\displaystyle{ \sim n }[/math]	[math]\displaystyle{ O(n) }[/math]	-
最好情况
最坏情况

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
正整数的分类	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
最大公约数理论	互质
算术基本定理	算术基本定理	标准质因数分解