CSP-J 入门级 · CSP 2020 入门级第一轮 第 19 题

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1.（质因数分解）给出正整数 $n$，请输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：输入 $n=120$，程序应该输出 2 2 2 3 5，表示：$120 = 2 \times 2 \times 2 \times 3 \times 5$。输入保证 $2\le n \le 10^9$。

提示：先从小到大枚举变量 $i$，然后用 $i$ 不停试除 $n$ 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;
int n, i;

int main() {
  scanf("%d", &n);
  for(i = ①; ② <=n; i ++){
    ③{
      printf("%d ", i);
      n = n / i;
    }
  }
  if(④)
    printf("%d ", ⑤);
  return 0;
}

1）①处应填（ ）

2）②处应填（ ）

3）③处应填（ )

4）④处应填（ ）

5）⑤处应填（ )

这题考质因数分解，核心就是从小到大枚举i，用i反复试除n，直到i*i>n为止，最后若n仍大于1则说明剩余一个大于根号n的质因子。

最容易错在把while(n%i==0)写成if(n%i==0)，导致同一个质因子只除一次，输出结果缺项；其次是循环条件写成i<=n，既浪费时间又可能漏掉大质因子；还有很多人忘了最后单独输出剩余的n。

考点与概念 质因数分解就是把一个数拆成若干质数相乘的形式。试除法是最朴素的思路：从小到大拿每个数去试除，能整除就除掉，并且要一直除到除不尽为止，这样才能保证每个质因子都被完整提取出来。

命题视角 这道题是 CSP 入门级的经典送分题，但命题人喜欢在细节上挖坑：一是考察你是否知道要“反复除”（while vs if），二是考察你是否知道循环可以优化到 i*i<=n（否则 n=10^9 时会超时），三是考察你是否记得最后可能还有一个大于根号 n 的质因子没输出。

逐空推演 ① 起始值：质因子最小是 2，所以 i 从 2 开始，选 C。 ② 循环终止：如果 i*i>n，说明剩下的数要么是 1，要么是一个大于 i 的质数，不会再有小于等于 i 的因子了，因此条件应为 i*i<=n，选 C。 ③ 内部逻辑：同一个质因子可能出现多次（比如 120 中有三个 2），必须用 while(n%i==0) 不停除，选 C。 ④ 最后判断：循环结束后，若 n 仍大于 1，说明它本身就是一个质因子（因为所有小于等于√原n的因子都已除尽），条件为 n>1，选 A。 ⑤ 输出剩余：直接输出此时的 n 即可，选 C。

完整代码

for(i = 2; i*i <= n; i++) {
    while(n % i == 0) {
        printf("%d ", i);
        n = n / i;
    }
}
if(n > 1)
    printf("%d ", n);

验证 拿样例 n=120 跑一遍：i=2 时 while 除三次，n 变成 15；i=3 时 while 除一次，n 变成 5；i=4 时 4*4=16>5 循环结束；最后 n=5>1，输出 5。结果 2 2 2 3 5，完全正确。

复杂度 最坏情况是 n 为质数，循环走到√n，整体 O(√n)，对于 10^9 约 3 万次迭代，轻松过。

考频与趋势 枚举法在题库里共考了 159 题，覆盖多个级别，其中 2026 年单年就有 13 题，2025 年 6 题，2024 年 6 题，呈现逐年上升的态势；数论基础类题目共 28 题，2020 年 4 题、2024 年 3 题、2026 年 11 题，也是近年热点；质数与合数相关题目共 52 题，2024 年高达 21 题，2025 年 13 题。这说明“质因数分解”这类数论入门题在 CSP 入门级和 GESP 三级、五级中非常高频。

预测 基于数据，未来两年（2027-2028）在 CSP 入门级和 GESP 三级、五级中出现类似的质因数分解或试除法优化题目的概率很大，很可能继续作为送分题或第一道大题出现。暂无足够依据预测是否会引入更复杂的分解算法（如 Pollard-Rho），但试除法的变体（如只求不同质因子个数、求最小质因子等）值得留意。