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

证明 p² 起筛和 √n 停止的依据,理解分段筛的进一步优化。

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

埃氏筛Sieve of Eratosthenes

从每个质数 p 的 p² 开始划去倍数,常见时间 O(n log log n)。

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

本课要建立的能力

证明 p² 起筛和 √n 停止的依据,理解分段筛的进一步优化。

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

01先把问题说具体

已经会按倍数标记,怎样避免从 2p 重复划掉很多早已处理过的合数?

02一步步得到方法

p² 之前的倍数已有更小因子

对质数 p,2p、3p、…、(p−1)p 的另一个因子小于 p,早已被更小质数的标记覆盖。因此可以直接从 p² 开始,而不会漏掉合数。

若合数 x≤n 的所有因子都大于 √n,它们的乘积会大于 n,矛盾;因此每个合数都有不超过 √n 的质因子。外层只需处理 p²≤n。

剩余候选可直接收集

外层停止不等于后面的数字没有检查过,而是所有合数已经收到至少一次标记。大于 √n 的 True 项一定是质数,可以直接输出。

n 很大时布尔数组仍占 O(n) 空间。分段筛先求 √n 内的质数,再按固定长度区间标记它们的倍数,控制工作内存;区间起点要对齐到不小于 L 且不小于 p² 的首个倍数。

从 p² 开始标记不会漏掉合数

p 的较小倍数 2p、3p 等,已经含有更小因子,之前轮次可以标掉。p² 是第一个可能还没被更小素因子处理的 p 的倍数,因此无需从2p重复开始。

当 p²>N 时,剩余未标记数都是素数:若某个剩余数是合数,它必有不超过自身平方根的素因子,已经应被处理。这解释了外层只需到平方根。

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

n=30。

步骤计算与状态为什么这样做
p=2,从 4 开始4,6,8,…,30排除偶合数
p=3,从 9 开始9,12,15,…,306 已由 2 处理
p=5,从 25 开始25,3010、15、20 早已标记
下一 p=6,p²>30结束外层收集全部 True

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

输出 [2,3,5,7,11,13,17,19,23,29]。

04为什么这个方法成立

  1. 对每个 p,p² 之前的合数倍数已被更小因子覆盖。
  2. 所有合数都有≤√n 的质因子,所以外层范围足够。
  3. 只标记真正倍数且不标 p 本身,保证质数保留。

05把推导翻译成代码

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

from math import isqrt
def eratosthenes(n):
    if n < 2:
        return []
    prime = bytearray([1])*(n+1)
    prime[0] = prime[1] = 0
    for p in range(2,isqrt(n)+1):
        if prime[p]:
            for x in range(p*p,n+1,p):
                prime[x] = 0
    return [x for x in range(2,n+1) if prime[x]]

逐个理解关键决定

isqrt(n)
整数平方根避免浮点边界误差。
range(p*p,n+1,p)
从第一个尚可能未被更小因子处理的倍数开始。

06时间、空间与实现范围

时间 O(n log log n),空间 O(n),优化主要减少常数而非把渐近界变成完全不同的量级。

bytearray 每项一个字节,比 Python 布尔对象引用列表更紧凑,但不是每项一位的位图。

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

从 p² 开始就把 p≤√n 的判断删掉又声明无重复成本

超过 √n 后没有需要标记的倍数,继续扫描虽可正确但浪费外层工作。

使用固定宽度整数时 p*p 溢出

上界很大时应采用足够宽类型或 p≤N/p 的判断方式,别让溢出改变循环条件。

08从手算到独立迁移

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

练习 1 · 复现与理解

n=49 时为什么必须处理 p=7?

需要一点提示

49 是完全平方数。

查看解析与答案

要划去 7²=49,所以范围必须包含整数平方根。

练习 2 · 边界与辨析

分段 [100,120],p=3 首个标记数?

需要一点提示

不小于 100 的 3 倍数。

查看解析与答案

102,且与 p²=9 取较大起点。

练习 3 · 变式与迁移

筛过一次如何快速回答很多 ≤n 的素性查询?

需要一点提示

保留什么而非只返回列表?

查看解析与答案

保留 prime 标记数组,每次按下标读取即可 O(1) 回答。

继续深入这个专题

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

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

理解之后,继续递进

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