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,…,30 | 6 已由 2 处理 |
| p=5,从 25 开始 | 25,30 | 10、15、20 早已标记 |
| 下一 p=6,p²>30 | 结束外层 | 收集全部 True |
窄屏可左右滑动表格,阅读完整计算与理由。
输出 [2,3,5,7,11,13,17,19,23,29]。
04为什么这个方法成立
- 对每个 p,p² 之前的合数倍数已被更小因子覆盖。
- 所有合数都有≤√n 的质因子,所以外层范围足够。
- 只标记真正倍数且不标 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
n=49 时为什么必须处理 p=7?
需要一点提示
49 是完全平方数。
查看解析与答案
要划去 7²=49,所以范围必须包含整数平方根。
分段 [100,120],p=3 首个标记数?
需要一点提示
不小于 100 的 3 倍数。
查看解析与答案
102,且与 p²=9 取较大起点。
筛过一次如何快速回答很多 ≤n 的素性查询?
需要一点提示
保留什么而非只返回列表?
查看解析与答案
保留 prime 标记数组,每次按下标读取即可 O(1) 回答。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂