数学、数论与组合 · HTML
数学 / 逻辑形态
筛法从每个未标记质数 p 标记其倍数；SPF[x] 记录 x 的最小质因子并反复除去。
识别信号
- 需要某范围全部质数
- 要分解许多不大的整数
- 答案依赖因数个数或质因子指数
- 逐数试除会重复工作
- 需判断互质或质因子集合
容易误判的相似信号
| Signal | Why it is different |
|---|
| 单个巨大整数 | 筛到平方根可能太大，应考虑更适合的大整数方法。 |
| 仅求两个数 GCD | 欧几里得更直接，无需展开质因子。 |
核心不变量
处理质数 p 后，其范围内倍数均被标记；SPF 版本中首次写入的因子就是最小质因子。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | is_prime 或 spf 数组、当前候选 p、可选质数列表。 |
| Transition | 遇到未标记 p 即确认质数，从 p² 开始标记倍数；分解时反复取 spf[x]。 |
| Frontier / order | 候选 p 递增；小于 p 的质因子影响已全部传播。 |
Python 骨架
def smallest_prime_factors(n):
spf = list(range(n+1))
if n >= 1: spf[1] = 1
for p in range(2, int(n**0.5)+1):
if spf[p] == p:
for x in range(p*p, n+1, p):
if spf[x] == x: spf[x] = p
return spf
def factorize(x, spf):
out = {}
while x > 1:
p = spf[x]
out[p] = out.get(p, 0) + 1
x //= p
return out
正确性思路
- 若 p 未被更小质数标记，则 p 为质数。
- 小于 p² 的 p 倍数已有更小因子，因此从 p² 开始不漏未标记合数。
- 首次写入 SPF 的质数按递增顺序出现，必为最小因子。
- 分解每次除去一个质因子，最终乘积恢复原数。
复杂度
| Time | Space | Parameters |
|---|
| 经典筛 O(n log log n)，SPF 分解每次 O(log x) | O(n) | n 为预处理上界，x<=n 为待分解数 |
边界条件
- 0 与 1 不是质数
- n<2 时循环为空
- p² 可能在固定宽度语言溢出
- 分解输入必须在表范围
- 重复质因子要累计指数
错误模式
| Pattern | Why it fails / fix |
|---|
| 从 2p 开始重复标记 | 正确但浪费，p² 前已处理。 |
| 把 1 当质数 | 初始化必须显式排除。 |
| SPF 被较大因子覆盖 | 只在尚未设置时写入。 |
选择与排除规则
- 范围内批量质数：筛法。
- 多次分解且上界适中：SPF。
- 单个小数：试除更省预处理。
- 单个极大数：不要盲目筛到上界。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 28=2²×7。 |
| Scenario | 预处理到 30 并分解 28。 |
| Walkthrough | SPF[28]=2，连续除两次后剩 7，SPF[7]=7。 |
Recall prompts
我的补充