PYTHON LESSON 073
考点精讲：约数家族总动员
掌握成对枚举约数的方法，会求约数个数与约数和，认识完全数与亲和数。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 成对枚举：找到 i 别漏搭档 n // i
- 完全平方数的中间约数只收一次
- 真约数 = 所有约数 − 自己
01 · 核心概念
成对枚举约数、约数个数与约数和、完全数
成对枚举约数、约数个数与约数和、完全数：从 1 到 n 逐个试除要循环 n 次，太慢。其实约数是成对出现的：i 是约数，n // i 一定也是约数。只枚举到 √n，每找到一个就收进一对，百万级的数也只要一千次循环。
GESP Python 5 级 · 初等数论GESP Python 5 级 · 约数与倍数流程图是算法的表示方法，不是 Python 语法。
02 · 语法与规则
先记住这 3 条，再开始写程序
成对枚举：找到 i 别漏搭档 n // i先准确读出这条写法的结构与作用。
完全平方数的中间约数只收一次换一组最小数据，手工推演一次结果。
真约数 = 所有约数 − 自己再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 约数研究所：成对枚举 + 约数和
def divisors(n):
"""成对枚举约数：小的一半顺着收，大的一半倒着补"""
small = []
big = []
i = 1
while i * i <= n:
if n % i == 0:
small.append(i)
if i * i != n: # 完全平方数的中间约数只收一次
big.append(n // i)
i = i + 1
return small + big[::-1]
for x in [28, 36, 97]:
ds = divisors(x)
print(x, "的约数：", ds)
print("约数个数：", len(ds), "，约数和：", sum(ds))
print("——————")
# 完全数探测：真约数（不含自己）之和等于自己
for x in [6, 12, 28, 496]:
proper = sum(divisors(x)) - x
if proper == x:
print(x, "是完全数！真约数和 =", proper)
else:
print(x, "不是完全数，真约数和 =", proper)28 的约数： [1, 2, 4, 7, 14, 28] 约数个数： 6 ，约数和： 56 36 的约数： [1, 2, 3, 4, 6, 9, 12, 18, 36] 约数个数： 9 ，约数和： 91 97 的约数： [1, 97] 约数个数： 2 ，约数和： 98 —————— 6 是完全数！真约数和 = 6 12 不是完全数，真约数和 = 16 28 是完全数！真约数和 = 28 496 是完全数！真约数和 = 496
成对枚举让每个约数只检查到 √n；约数求和正是考级模拟卷“亲和数”一题的基本功。
04 · 逐步理解
每一步只解决一个问题
- 01
为什么要成对枚举
从 1 到 n 逐个试除要循环 n 次，太慢。其实约数是成对出现的：i 是约数，n // i 一定也是约数。只枚举到 √n，每找到一个就收进一对，百万级的数也只要一千次循环。
if n % i == 0: small.append(i) big.append(n // i) - 02
小心完全平方数
36 = 6 × 6，中间约数 6 的搭档还是 6 自己。如果不加判断，6 会被收进两次，约数个数和约数和全部算错。所以搭档与自己相等时，只收一个。
if i * i != n: big.append(n // i) - 03
两半拼回完整名单
small 从小到大收小约数，big 从大到小存进了它们的搭档。把 big 反转接在 small 后面，约数名单就整整齐齐。切片 [::-1] 是反转列表的惯用写法。
return small + big[::-1] - 04
约数和与真约数
约数和就是整个名单求和；不含自己的叫真约数和，等于总和减去 n。考级模拟卷里的亲和数题，考的正是真约数求和这一个函数。
proper = sum(divisors(n)) - n - 05
完全数与亲和数
真约数和恰好等于自己的数叫完全数，6、28、496 都是；你中有我、我中有你，真约数和互相等于对方的，就是著名的亲和数 220 和 284。数论的浪漫都藏在约数里。
- 06
动手挑战
用 divisors 找出 1000 以内的所有完全数（答案只有 6、28、496 三个）；再算一算 220 和 284 是不是一对亲和数，为后面的例题精练热身。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行研究所，盘点 28 和 36 的约数
- 2检查 36 的约数 6 有没有被重复收进名单
- 3找出 6 到 496 里的完全数
- 4挑战：口算 97 的约数和并和程序核对
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 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 的约数或模数非质数，必须先明确数学定义。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
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 码点序列长度。
完成检查