专题进阶 · 数学算法推荐总顺序 · 第 97 / 148 课

把重复试除转成批量标记,区分单个素性判断与区间内全部质数。

先学会这些,再进入本课 数组 模运算
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

质数筛Prime Sieve

批量筛除合数比对每个数独立试除更高效,空间通常随上界增长。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把重复试除转成批量标记,区分单个素性判断与区间内全部质数。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

找出 2 到 20 的全部质数。对每个数都独立试除,会重复检查大量相同因子。

02一步步得到方法

一个质数可以一次排除整串合数

建立布尔数组 alive,先将 2..n 视为候选。遇到仍未被划去的 p,就知道 p 为质数,再划去它的 2p、3p、4p 等倍数。一个标记过程同时给许多数字提供合数证据。

0 与 1 不属于质数,必须单独设为 False。质数的定义是大于 1 且正因子只有 1 和自身,不能把 1 当作起始质数来划掉所有元素。

为什么未划去的候选一定是质数

若 p 为合数,则存在小于 p 的质因子 q;扫描到 p 之前已经处理 q 并划去其倍数,因此 p 不可能还保持 True。这就是按从小到大扫描的正确性依据。

本课先从 2p 开始划,便于看懂筛的机制。下一课埃氏筛再证明可以从 p² 开始,并把外层限制到 √n,减少重复标记。

一次性回答一批素性问题

逐个判断每个数是否为素数,会反复试除相同的小因子。筛法让一个已知素数一次标掉其所有倍数,把大量独立问题组织成共享工作。

若只判断一个极大整数是否素数,建立从0到它的筛表可能不可行;若需要小于上界的全部素数或大量重复查询,预处理成本则可以被摊薄。选择方法前先看查询形态。

03把一个小例子完全算清楚

筛 2..20。

步骤计算与状态为什么这样做
处理 2划去 4,6,8,10,12,14,16,18,20保留 2 本身
处理 3划去 6,9,12,15,18有些已被划过
处理 5、7…继续划倍数未划去的候选为质数

窄屏可左右滑动表格,阅读完整计算与理由。

最终 [2,3,5,7,11,13,17,19]。

04为什么这个方法成立

  1. 每次只划去大于 p 的 p 倍数,因此不会误删质数 p。
  2. 所有合数都有更小质因子,最终会被某次标记覆盖。
  3. 未被划去且大于 1 的数恰好是质数。

05把推导翻译成代码

Python · 可独立运行的教学实现

def prime_sieve(n):
    if n < 2:
        return []
    alive = [True]*(n+1)
    alive[0] = alive[1] = False
    for p in range(2,n+1):
        if alive[p]:
            for multiple in range(2*p,n+1,p):
                alive[multiple] = False
    return [p for p in range(2,n+1) if alive[p]]

逐个理解关键决定

range(2*p,n+1,p)
从第二个倍数开始,不能把 p 自身划掉。
if alive[p]
只有质数才启动标记,合数无需重复当作筛基数。

06时间、空间与实现范围

总标记次数由质数倒数和控制,为 O(n log log n),另有 O(n) 扫描,空间 O(n)。

相比逐数试除,筛适合一次求整个上界范围;只判断一个超大整数时不应开到该整数大小的数组。

07改变条件,检查哪里会出错

把 1 当质数

它会破坏因子分解与筛的逻辑,应按定义排除。

把筛表大小只按素数数量估算

普通筛仍为每个整数位置保留标记,空间按上界N计而非按最终素数个数计。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

n=1 输出什么?

需要一点提示

没有大于 1 的候选。

查看解析与答案

空列表。

练习 2 · 边界与辨析

9 在哪一步被删除?

需要一点提示

最小质因子。

查看解析与答案

处理 3 时。

练习 3 · 变式与迁移

只查一个 10^12 附近的数,还适合完整筛到它吗?

需要一点提示

估算数组长度。

查看解析与答案

通常不适合,应按任务选择试除、概率素性检验等方法;筛的优势是批量。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。