查看“︁线性筛”︁的源代码

[[分类:整除理论]]
[[分类:质数分布问题]]
[[分类:数论算法]]
[[分类:以 Euler 命名]]
{{InfoBox
|name=线性筛
|eng_name=linear seive
|aliases=欧拉筛法,欧拉筛,线性筛法
}}
'''线性筛法'''('''linear seive''')或'''线性筛'''，也称'''<ins>欧拉</ins>筛'''，是找出小于某正整数的全部[[质数]]的算法。这一算法是 [[Eratosthenes 筛法]]的改进版，因时间复杂度降低到[[线性复杂度]]而得名。

== 改进原理 ==

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

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

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

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

== 算法 ==

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

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

直到所有的数都被遍历。

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

=== 举例 ===

为了便于理解，这里将正整数 <math>n</math> 按照其[[质因子个数函数|质因数个数 <math>\Omega(n)</math>]] 分类：

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

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

=== 伪代码 ===

<syntaxhighlight>
过程 线性筛
别名 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
</syntaxhighlight>

❶ 这里可以改为 <syntaxhighlight inline>2k ≤ n</syntaxhighlight> 。

=== 复杂度 ===

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

{{固定复杂度|<math>\sim n</math>|<math>O(n)</math>}}


{{整除与质数}}