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为什么这个方法成立
- 每次只划去大于 p 的 p 倍数,因此不会误删质数 p。
- 所有合数都有更小质因子,最终会被某次标记覆盖。
- 未被划去且大于 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
n=1 输出什么?
需要一点提示
没有大于 1 的候选。
查看解析与答案
空列表。
9 在哪一步被删除?
需要一点提示
最小质因子。
查看解析与答案
处理 3 时。
只查一个 10^12 附近的数,还适合完整筛到它吗?
需要一点提示
估算数组长度。
查看解析与答案
通常不适合,应按任务选择试除、概率素性检验等方法;筛的优势是批量。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂