GESP 六级 · GESP 六级样题（C++ 组） 第 14 题

现希望存储整数 $N$ 的所有质因子，请问其空间复杂度上界为是（ ）。

这题考的是质因子个数与数值大小的关系。拿到题先想：N 最小能拆成多少个 2 相乘？由 2^k ≤ N 得 k ≤ log₂N，所以存质因子只需 O(log N) 空间，答案选 B。

很多考生会混淆“质因子”和“约数”。约数个数确实可能达到 O(N)（如 N 本身），但质因子个数受限于对数。还有人会死记硬背约数个数公式，误以为质因子个数也有类似平方根或线性增长，从而选错 C 或 D。记住：质因子个数上界是 log N，约数个数上界是 N，两者量级完全不同。

【考点定位】 本题属于 GESP 六级《算法复杂度分析》模块，同时涉及数论基础中的质因子分解。命题人特意用“质因子个数”而非“约数个数”，旨在卡住大量考生对“因子”与“约数”的混淆，以及空间复杂度与数值大小的直觉偏差。

【核心概念与推导】 存储整数 N 的所有质因子（计重数），本质是统计 N 的标准分解式中质因子的总个数。我们要找的是这个个数的上界。

最直观的思路是考虑极端情况：N 由最小的质数 2 重复相乘得到，即 N = 2^k。此时质因子个数 k = log₂N。对于任意 N，若其质因子个数为 k，则必有 2^k ≤ N（因为 2 是最小质数），故 k ≤ log₂N。因此，无论 N 多大，其质因子个数绝不会超过 log₂N。这意味着存储这些因子所需的机器字数量级为 O(log N)。

【命题视角与避坑】 A 选项 O(log log N) 通常对应的是不同质因子的个数（即 N 的无平方因子部分），而非计重数的总个数，这是常见的偷换概念。C 选项 O(sqrt N) 容易让人联想到试除法分解的复杂度，但题目问的是存储空间，而非算法时间。D 选项 O(N) 则是把“质因子”误当成“约数”后的结果——约数个数确实可能达到 O(N)（如 N 本身），但质因子个数远小于 N。

【考频与趋势】 数论基础在题库中仅考了 28 题，且分布极度分散：2024 年 3 题、2026 年 11 题，其他年份零星分布。复杂度分析更是只考了 39 题，且全部集中在 2026 年。这说明该考点处于“低频但高价值”状态，命题人倾向于在决赛或高级别考试中通过概念辨析来区分考生。GESP 六级作为算法与数学的交叉点，常在此处设陷阱。

【预测】 基于近年数论与复杂度分析在高级别考试中频繁出现“概念辨析”题型（如 2026 年大量考数论），未来六级及以上考试极可能继续以“质因子 vs 约数”、“时间 vs 空间”的对比形式出题，甚至可能结合大数分解的实际场景考察对数空间的理解。暂无足够依据预测具体年份或题目形式，但方向明确：概念混淆仍是重灾区。