PYTHON LESSON 068
质因数分解机
理解唯一分解定理，会编程分解质因数，并用指数公式求约数个数。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 从 2 开始试除，除尽就接着除
- while i * i <= m 控制试除范围
- 约数个数 = 各质因数指数加 1 相乘
01 · 核心概念
唯一分解定理与试除分解
唯一分解定理与试除分解：算术基本定理告诉我们：每个大于 1 的整数，都能唯一地写成质数的乘积。360 的身份证是 2³ × 3² × 5，全世界找不到第二张一样的——这是整个数论大厦的地基。
GESP Python 5 级 · 唯一分解定理GESP Python 5 级 · 同余与模运算大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
从 2 开始试除，除尽就接着除先准确读出这条写法的结构与作用。
while i * i <= m 控制试除范围换一组最小数据，手工推演一次结果。
约数个数 = 各质因数指数加 1 相乘再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 质因数分解机：唯一分解定理
def factorize(n):
"""把 n 分解质因数，返回 [(质因数, 次数), ...]"""
parts = []
i = 2
m = n
while i * i <= m:
count = 0
while m % i == 0:
m = m // i
count = count + 1
if count > 0:
parts.append((i, count))
i = i + 1
if m > 1: # 剩下的 m 本身是一个大质因数
parts.append((m, 1))
return parts
def show(n):
parts = factorize(n)
text = " × ".join(f"{p}^{c}" if c > 1 else f"{p}" for p, c in parts)
print(n, "=", text)
divisors = 1
for p, c in parts:
divisors = divisors * (c + 1) # 每个质因数可以选 0~c 个
print(n, "的约数个数：", divisors)
for num in [360, 1001, 97]:
show(num)360 = 2^3 × 3^2 × 5 360 的约数个数： 24 1001 = 7 × 11 × 13 1001 的约数个数： 8 97 = 97 97 的约数个数： 2
唯一分解定理：每个大于 1 的整数，质因数分解结果唯一（不计顺序）。
04 · 逐步理解
每一步只解决一个问题
- 01
唯一分解定理
算术基本定理告诉我们：每个大于 1 的整数，都能唯一地写成质数的乘积。360 的身份证是 2³ × 3² × 5，全世界找不到第二张一样的——这是整个数论大厦的地基。
- 02
试除分解的流程
从 2 开始试：能除尽就计数加 1、把 m 除掉这个因子，接着再试同一个 i；除不尽就换 i + 1。每个质因数都会被“榨干”后才轮到下一个。
while m % i == 0: m = m // i count = count + 1 - 03
为什么除到 √m 就收工
和质数判定同理：若 m 还有因数，必有一个不超过 √m。循环结束时若 m > 1，剩下的 m 本身就是最后一个大质因数，别忘了收进名单。
if m > 1: parts.append((m, 1)) - 04
用（质因数, 次数）记账
parts 列表里每项是一个小元组 (p, c)，表示质因数 p 出现了 c 次。打印时用条件表达式：次数大于 1 写成 p^c，否则只写 p。
f"{p}^{c}" if c > 1 else f"{p}" - 05
约数个数公式
360 = 2³ × 3² × 5。每个约数就是“2 选 0~3 个、3 选 0~2 个、5 选 0~1 个”的一种选法，共 4 × 3 × 2 = 24 种。指数各加 1 再相乘，约数个数手到擒来。
divisors = divisors * (c + 1) - 06
同余的小实验
模运算还有一个绝活：7¹ 末位 7、7² 末位 9、7³ 末位 3、7⁴ 末位 1，然后循环。所以 7 的幂末位以 4 为周期——“同余找周期”能秒答超大幂的末位，竞赛常客。
last = 1 for k in range(1, 5): last = last * 7 % 10 print(last)
05 · 练习与检验
自己写出来，才算真正学会
- 1运行分解机，拆解 360 的身份证
- 2分解 1001，验证身份证唯一
- 3算出 360 一共有多少个约数
- 4挑战：找 100 以内约数最多的数
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
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。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。
完成检查