北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 28 题

完善程序（共 5 道小题，每小题 2 分，共计 10 分）

质因数分解：给定一个正整数 $n$，输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：当 $n = 120$ 时程序应该输出 $2\ 2\ 2\ 3\ 5$，表示：$120 = 2 \times 2 \times 2 \times 3 \times 5$。

输入保证 $2 \leq n \leq 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. 空缺 ① 处应该填 ( ) A. 1 B. n-1 C. 2 D. 0

2. 空缺 ② 处应该填 ( ) A. n/i B. n/(i*i) C. i*i D. i*i*i

3. 空缺 ③ 处应该填 ( ) A. if(n%i==0) B. if(i*i<=n) C. while(n%i==0) D. while(i*i<=n)

4. 空缺 ④ 处应该填 ( ) A. n>1 B. n<=1 C. i<n/i D. i+i<=n

5. 空缺 ⑤ 处应该填 ( ) A. 2 B. n/i C. n D. i

这题考质因数分解。拿到题先想：从小到大枚举 i，一旦 i 能整除 n，就不断除尽（while），同时 i 只跑 i*i<=n 就够，剩下的若大于 1 就是最后一个大质因子。

最容易错在把循环条件写成 i*i<=n 却忘了外层循环要跑完，导致大质因子漏判；或者在试除时用了 if 而不是 while，只除了一次，n 里还残留 i 的幂次；还有人会误以为 i 从 1 开始，导致输出 1 这个非质数；最后那个 if 判断写反（n<=1 时输出）也会把大因子漏掉。

这道题考查的是基础的质因数分解算法，核心就是利用“从小到大试除”和“除尽”两个思想。命题人出这种完善程序题，就是想看你是否真正理解算法流程，而不是死记硬背代码，所以每个空都卡在关键逻辑点上，爱挖坑的地方通常就是大家容易想当然的地方。拿到题，我们的思考心法应该是：先确定枚举范围，再处理整除情况，最后收尾处理剩余部分。具体怎么推呢？

首先看空缺①。题目要求从小到大输出所有质因子。我们知道 1 不是质数，所以枚举 i 必须从 2 开始。如果填 1，程序就会先输出 1，这直接违背了质因数分解的定义。选项 D 是 0，更离谱；选项 B 是 n-1，枚举顺序完全反了。所以①只能填 C（2）。这一步看似简单，但很多初学者会忽略“质数从 2 开始”这个基本常识，掉进坑里。

接着看空缺②。这是外层循环的结束条件。质因数分解有个重要优化：如果一个数 n 有质因子，那么最小的那个质因子一定不超过√n。因此，当我们枚举到 i*i > n 时，如果 n 还没变成 1，说明剩下的 n 本身就是一个质数。所以循环条件应该是 i*i <= n。选项 A 是 n/i，这没意义；选项 B 是 n/(i*i)，逻辑混乱；选项 D 是 while(i*i<=n)，那是循环体里的条件，不是 for 循环的结束条件。所以②填 C（i*i）。这里命题人挖的坑就是让你混淆循环头和循环体里的判断条件。

再看空缺③。这是处理整除的核心逻辑。当 i 能整除 n 时，我们不能只用一次 if(n%i==0)，因为 n 里可能含有 i 的多次幂（比如 120 里有 2^3）。必须用 while(n%i==0) 不断除尽，每除一次就输出一遍 i，直到 n 不再被 i 整除为止。选项 A 是 if，除不尽；选项 B 和 D 都是判断条件，不是执行语句。所以③填 C（while(n%i==0)）。这是本题最容易错的点之一，很多人会误以为“试除一次就够了”，结果输出结果少了因子。

最后看空缺④和⑤。当循环结束时，n 可能已经变成了 1（所有因子都分解完了），也可能还大于 1（剩下的就是最后一个大质因子）。我们需要判断是否还有剩余。如果 n > 1，说明还有一个因子没输出，直接输出 n 即可。选项 B 是 n<=1，逻辑反了；选项 C 和 D 都是奇怪的比较式。所以④填 A（n>1）。对应的⑤自然就是输出剩余的 n，填 C（n）。这一步是收尾，很多人会漏掉这个判断，导致程序对质数或大质因子输入失效。

总结一下，这道题的算法主线非常清晰：从 2 开始枚举，只要 i*i<=n 就继续，遇到整除就 while 除尽并输出，循环结束后若 n>1 再输出 n。命题人喜欢在这种基础题里考细节，比如枚举起点、循环条件、除尽逻辑、剩余判断，每一个小坑都能让没想清楚的人丢分。从考频和趋势来看，质因数分解是历届信息学竞赛（CSP-J/S、NOIP）的高频考点，几乎每年必出，而且出题形式越来越灵活，从单纯的输出到完善程序、从求因子个数到求因子和，考察深度在增加。基于历年数据，未来这类题目大概率会继续以“完善程序”或“求特定统计量”的形式出现，难度维持在中等偏上，重点依然是考察对算法流程的完整理解，而不是单纯套公式。因此，复习时务必把质因数分解的手动模拟过程练熟，确保每一步逻辑都经得起推敲。