PYTHON LESSON 067
素数筛子工厂
掌握埃氏筛法，理解“确认质数就筛掉其倍数”的思想，知道线性筛的优化方向。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 布尔列表当筛子：is_prime[i]
- 从 i*i 开始标记倍数
- 切片收集所有幸存的下标
01 · 核心概念
埃氏筛法与线性筛思想
埃氏筛法与线性筛思想：准备一张 2~n 的名单。2 是质数，把 2 的倍数全部划掉；下一个没被划掉的是 3，把 3 的倍数全部划掉……一轮下来，幸存的全是质数。这就是两千多年前的埃拉托斯特尼筛法。
GESP Python 5 级 · 素数筛法大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
布尔列表当筛子：is_prime[i]先准确读出这条写法的结构与作用。
从 i*i 开始标记倍数换一组最小数据，手工推演一次结果。
切片收集所有幸存的下标再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 素数筛子工厂：埃拉托斯特尼筛法
def sieve(n):
"""筛出 2~n 的所有质数：确认一个质数，就筛掉它的所有倍数"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0 和 1 不是质数
for i in range(2, n + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i): # 从 i*i 开始筛才不算重复工
is_prime[j] = False
return [x for x in range(2, n + 1) if is_prime[x]]
primes = sieve(50)
print("50 以内的质数：", primes)
big = sieve(1000)
print("1000 以内共有", len(big), "个质数")
print("其中最大的 5 个：", big[-5:])50 以内的质数： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 1000 以内共有 168 个质数 其中最大的 5 个： [971, 977, 983, 991, 997]
筛法像“消消乐”：每确认一个质数，就一次性消掉它的所有倍数。
04 · 逐步理解
每一步只解决一个问题
- 01
试除法的瓶颈
第 33 课的试除法判定一个数很快，但“找出 100 万以内所有质数”要对每个数都审一遍，重复劳动太多。换个思路：不查每个数，而是让质数自己“举报”倍数。
- 02
筛子的核心思想
准备一张 2~n 的名单。2 是质数，把 2 的倍数全部划掉；下一个没被划掉的是 3，把 3 的倍数全部划掉……一轮下来，幸存的全是质数。这就是两千多年前的埃拉托斯特尼筛法。
is_prime = [True] * (n + 1) - 03
布尔列表当筛网
is_prime[i] 为 True 表示“i 目前还是质数候选”。划掉 j 就是 is_prime[j] = False。下标本身就是数字，连查找都省了——这是用空间换时间的经典案例。
for j in range(i * i, n + 1, i): is_prime[j] = False - 04
为什么从 i*i 开始筛
i 的倍数 i×2、i×3……i×(i-1) 早就被比 i 小的质数筛过了，从 i×i 开始才不重复劳动。同理，外层 i 只需走到 √n 附近，筛子就收工。
- 05
数一数筛了多少次
给内外循环各加一个计数器，对比“筛法标记次数”和“逐个试除次数”。n 越大差距越惊人——这就是算法的力量：同样的答案，天壤之别的代价。
- 06
线性筛（了解）
埃氏筛里一个合数可能被多个质数重复筛（比如 12 被 2 和 3 都筛）。线性筛让每个合数只被它的最小质因数筛一次，更快一步，GESP 更高等级再见它。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行筛子，看 50 以内的质数名单
- 2改成筛 1000 以内，数一数个数
- 3想一想：为什么从 i*i 开始筛
- 4对比试除法和筛法各标记了多少次
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
完成检查