GESP 七级 · GESP 202406 C++ 七级 第 18 题

唯一分解定理（算术基本定理）指出，每个大于 $1$ 的自然数都可以唯一地分解成若干个素数的乘积。因此，我们可以很容易的对给定的自然数 $n$ 进行质因数分解，时间复杂度仅为 $O(\log(n))$。

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】唯一分解定理｜算法复杂度分析｜命题陷阱识别

考纲定位 本题考查 GESP 七级《数论基础》模块中“唯一分解定理”与“算法复杂度”的交叉考点。命题人故意将数论定理与算法复杂度混淆，卡住的是考生对“理论正确性”与“实现复杂度”的区分——许多考生只背定理结论，却忽略算法实际效率。

解题思维 正确思路应先验证两句话：第一句“每个大于 1 的自然数可唯一分解为素数乘积”是算术基本定理，成立；第二句“时间复杂度 O(log n)"则完全错误。因为质因数分解并非简单的计数或遍历，最朴素的试除法复杂度是 O(√n)，而更高效的 Pollard's rho 算法复杂度约为 O(n^(1/4)log n)，无论如何都不可能达到 O(log n)。

陷阱拆解 命题人设的陷阱很阴险：前半句是数论真命题，后半句却把“质因数分解”与“对数级运算”强行绑定。O(log n) 的运算是像取对数、模幂这样的简单操作，而分解素因数必须逐个试除或递归搜索，其复杂度必然与 n 的位数或平方根相关。若只背“唯一分解定理”而不理解其算法实现，就会误选 A。

反命题思维 若将“时间复杂度 O(log n)"改为“求 n 的各位数字之和”，答案就变成 A，因为求和确实是 O(log n)（与 n 的位数成正比）。反之，若把“唯一分解定理”的前提改成“每个大于 1 的自然数可分解为若干整数的乘积”，结论 A 依然成立，但复杂度描述就毫无意义——命题人正是靠这种偷换概念来制造陷阱。