PYTHON LESSON 065
质数探案
理解质数与合数的定义，掌握试除法及“只除到平方根”的关键优化。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 质数：只有 1 和它本身两个约数
- for 试除 2 到 √n
- 找到因数立刻 return，绝不多算
01 · 核心概念
质数与合数、试除法判定
质数与合数、试除法判定：质数（素数）只有 1 和它本身两个约数，比如 2、3、5、7；其余的叫合数。特别注意：1 既不是质数也不是合数，2 是唯一的偶质数——这两个是考试最爱挖的坑。
GESP Python 5 级 · 初等数论GESP Python 5 级 · 质数判定大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
质数：只有 1 和它本身两个约数先准确读出这条写法的结构与作用。
for 试除 2 到 √n换一组最小数据，手工推演一次结果。
找到因数立刻 return，绝不多算再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 质数探案：嫌疑人审查系统
import math
def is_prime(n):
"""判定 n 是否为质数（试除到平方根为止）"""
if n < 2:
return False
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
return False
return True
# 审查四个嫌疑人
for x in [29, 51, 97, 341]:
if is_prime(x):
print(x, "：确认是真的质数")
else:
print(x, "：是伪装的合数！")
print("——————")
# 给 50 以内的数全部建档
primes = []
for x in range(2, 51):
if is_prime(x):
primes.append(x)
print("50 以内的质数：", primes)
print("一共有", len(primes), "个")29 ：确认是真的质数 51 ：是伪装的合数！ 97 ：确认是真的质数 341 ：是伪装的合数！ —————— 50 以内的质数： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 一共有 15 个
341 = 11 × 31，是著名的“伪装者”；试除只需到 √n，因为因数总是成对出现。
04 · 逐步理解
每一步只解决一个问题
- 01
质数与合数
质数（素数）只有 1 和它本身两个约数，比如 2、3、5、7；其余的叫合数。特别注意：1 既不是质数也不是合数，2 是唯一的偶质数——这两个是考试最爱挖的坑。
- 02
最朴素的试除
要判定 n，就让 2、3、4……n-1 挨个试除，谁整除了 n，n 就是合数。办法正确但太慢：判定一千万附近的数，要试近一千万次。
for i in range(2, n): if n % i == 0: return False - 03
关键优化：只试到 √n
因数成对出现：若 n = a × b 且 a ≤ b，那么 a 一定不超过 √n。所以试到平方根还没找到因数，就永远找不到了。math.isqrt(n) 专门求整数平方根，又快又准。
for i in range(2, math.isqrt(n) + 1): - 04
找到即定罪
一旦发现 n % i == 0，立刻 return False 收工，绝不多算一次。这个“提前离场”的习惯，在循环程序里能省下大量时间。
if n % i == 0: return False - 05
奇偶性再加速（了解）
2 以外的质数都是奇数，所以可以先判 2，再只试 3、5、7……这些奇数，又能省一半功夫。“利用奇偶性剪枝”是数论程序的常见加速手段。
if n % 2 == 0: return n == 2 - 06
破案挑战
用你写的 is_prime 判定 999983（它是质数）和 999999（不是）。再数一数 100 以内有几个质数——答案是 25 个，和程序对上了吗？
05 · 练习与检验
自己写出来，才算真正学会
- 1运行审查系统，看四个嫌疑人的判决
- 2给 100 以内的数全部建档
- 3把试除上限改回 n-1，对比循环圈数
- 4挑战判定大数 999983
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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
完成检查