CSP-J阅读题中的筛法与最小质因子表：从数组语义到质因数分解的完整拆解

2022年CCF非专业级别软件能力认证第一轮（CSP-J1）入门级C++语言试题里，阅读程序部分的第1题，是每年初赛阅读题中信息密度最高、最值得反复咀嚼的一道。它看起来只是一段二十多行的筛法代码，却能一口气考到数组语义、循环边界、质因数分解和“程序到底在干什么”的宏观判断，很多选手现场「代码看懂了，题目做不对」，问题恰恰出在不会用手工模拟去验证自己的猜测。

这篇文章我按考场原题还原这段C++代码，把每一行变量含义、每一个判断选项的推导过程、以及这类阅读程序题通用的“三步拆解法”完整捋一遍。适合正在备战CSP-J的选手、带信息学竞赛的老师，以及所有想把筛法真正吃透的C++初学者——看完你不仅能拿下这一题，以后再遇到类似代码，也能一眼看穿它的底层逻辑。

1. 原题回放与这道题的“命门”

1.1 我按考场原题还原的代码

先把我记忆中的2022年CSP-J1阅读程序第1题核心代码完整贴出来。每年真题细节可能有个别行号差异，但算法骨架就是这个样子：

#include <iostream> using namespace std; int main() { short a[1010] = {0}; int n; cin >> n; for (int i = 2; i <= n; i++) { if (a[i] == 0) { a[i] = i; if (i * i <= n) { for (int j = i; j * i <= n; j++) { if (a[j * i] == 0) a[j * i] = i; } } } } for (int i = 2; i <= n; i++) { if (a[i] == i) cout << i << " "; else { int t = i; while (t > 1) { cout << a[t] << " "; t = t / a[t]; } } cout << endl; } return 0; }

这段代码非常短，但里面藏着四个层面的东西：数组初始化、埃氏筛变体、最短质因子表的构建、质因数分解的输出。考场上最忌讳的就是“看个大概就去做题”，因为判断题和选择题考察的恰恰是那些容易被“大概”掩盖的边界和语义。

1.2 这道题到底在考什么：五个知识点一张网

我给这道题画过一张考点地图，基本覆盖了初赛阅读程序的主流出题角度：

• 数组初始化与类型语义：short a[1010] = {0}这个声明，决定了数组元素默认值、可访问下标范围、以及 short 类型的存储上限。
• 筛法思想的变体：这不是让你背“埃氏筛模板”，而是要求你理解a[i] == 0到底在判断什么，内层循环在给谁打标记。
• 最小质因子的记录逻辑：a[j * i] = i不是随意赋值，而是保证每个合数只被它最小的质因子标记一次。
• 循环边界与整数溢出：i * i <= n、j * i <= n两处边界，稍不留神就会推出错误结论；i * i在 n 较大时还有 int 溢出风险。
• 质因数分解的输出还原：第二段循环用while (t > 1)配合t = t / a[t]，本质上是沿着最小质因子表一步步把质因数拆出来。

说白了，这一题不是“背模板能拿分”的题目，而是考察你有没有真正动手模拟过程、理解数组里每个元素含义的思维习惯。接下来我从算法内核开始，一层层拆给你看。

2. 算法内核拆解：a数组不是筛，是一张“最小质因子表”

2.1 先回答最关键的问题：a[i]里到底存的是什么

很多初学者看到short a[1010] = {0}，第一反应是“这是一个标记数组，标记谁被筛掉了”。这个理解只能说对了一半，而且很容易误导后面的判断。

实际上，这个程序里的a[i]存的是i 的最小质因子，而不是简单的“已筛标记”。我们可以分三种情况看：

• 如果a[i] == 0，说明 i 还没有被任何比它小的质数标记过，i 是一个尚未处理的数。
• 如果a[i] == i，说明 i 的最小质因子就是它自己，也就是说 i 是一个质数。
• 如果a[i] == p，其中 p < i，说明 p 是 i 的最小质因子，i 是一个合数。

举个例子：n=10 时，程序运行结束后a[6] = 2、a[9] = 3、a[7] = 7。6 的最小质因子是 2，9 的最小质因子是 3，而 7 是质数，最小质因子是它自己，所以a[7] = 7。

你可以这样类比：假设有一排空房间，编号从 2 到 n。房间管理员从 2 号开始挨个检查，如果发现某个房间的门还是关着的（a[i] == 0），就打开门，在门牌上写上自己的编号（a[i] = i），然后去把编号比自己大的所有倍数房间都写上自己的编号（a[j*i] = i），当然如果那个房间已经有人的名字了就不再写。这样一来，每个房间门牌上留下的都是“第一个来敲门的编号”，也就是最小质因子。

这个类比非常关键，因为理解了a[i]的语义之后，后面所有判断题、选择题都不再是“猜”，而是可以靠推理得出。

2.2 外层循环为什么只看 a[i] == 0 的数

继续看外层循环：

for (int i = 2; i <= n; i++) { if (a[i] == 0) { a[i] = i; // 内层标记倍数的逻辑 } }

当 i 从小到大遍历时，如果a[i] != 0，说明 i 已经被某个更小的质因子标记过了，也就是说 i 是一个合数。此时程序跳过它，不进入内层循环。这其实就是埃氏筛的精髓：只有质数才有资格作为“筛子”去标记它的倍数。

为什么合数不能作为筛子？因为合数的最小质因子一定比它本身小，既然它已经被更小的质数标记过，那么它的所有倍数也一定早就被那个更小的质数标记过了，重复标记没有任何意义。比如 i=6 时，a[6]=2，6 是合数，而 6 的倍数比如 12、18 等，早在 i=2 或 i=3 的时候就已经被处理过（甚至会被标记上最小质因子），所以跳过 6 完全不影响结果，反而节省了时间。

这里有一个小细节值得注意：a[i] = i这一行是在if (a[i] == 0)分支内执行的，所以它只会给“当前这个数没被更小质数标记过”的数赋值。这个数必然是质数。于是我们可以放心地说：当程序执行到 a[i] == i 时，i 是质数。这个结论在第二段输出循环里会被反复用到。

2.3 被很多人问爆的 i*i <= n 到底能不能删

原题有一道判断题，问的大概是：把if (i * i <= n)这一层判断删掉，程序输出结果是否不变。正确答案是：不变，这个判断删掉不影响任何输出。这个结论让很多人意外，因为直觉上“删掉一个判断怎么可能没影响”。

我们来推导一下。内层循环长这样：

for (int j = i; j * i <= n; j++) { if (a[j * i] == 0) a[j * i] = i; }

注意内层循环的初始条件是j = i，所以内层循环执行的第一个判断就是i * i <= n。也就是说，就算把外层的if (i * i <= n)完全删掉，当i * i > n时，内层循环的第一次条件判断就会失败，循环体一次都不会执行。

所以外层那个 if 其实是“冗余”的。它不是 bug，而是写代码的人为了逻辑更清晰、或者为了省掉一次无意义的循环入口判断而写的。但它的存在恰恰成了出题人的陷阱——很多考生觉得“删掉这个判断肯定影响程序效率或结果”，实际上效率层面几乎没差别，结果层面完全没差别。

这里还牵出一个更深的考点：如果把判断条件换成i <= sqrt(n)，会发生什么？C++ 里 sqrt 返回的是浮点数，和整数比较有精度问题，而且每次外层循环都要算一次 sqrt，反而更慢。写成i * i <= n是为了避免浮点误差，但前提是i * i不能溢出 int。如果 n 大到一定程度，比如 n 接近 10 万，i * i仍然安全；但如果 n 是 10 亿级别的，i * i就可能超过 int 上限导致溢出。这也是竞赛里常考的“边界敏感型”问题，后面我会专门讲。

2.4 short 数组的容量陷阱

代码第一行用了short a[1010]，而不是更常见的int a[1010]，这个设计可是有讲究的。

short 类型在绝大多数 C++ 实现里占 2 字节，能表示的范围是 -32768 到 32767。也就是说，只要 n 不超过 32767，a[i]里存的最小质因子值就不会超范围，用 short 完全够。但如果哪天 n 输入得很大，比如 n = 50000，那么当 i = 49999 是质数时，a[49999] = 49999，49999 已经超过了 short 的上限 32767，会发生溢出，存进去的值就不是 49999 了。

不过在原题的典型数据范围（n <= 1000 或 n <= 10000）里，short 是安全的。那为什么出题人要用 short？我觉得有两个考虑：

一是考察选手对类型范围的敏感度。判断题里完全可能埋伏“如果 n 大于 32767，程序可能出错”这种选项，如果你对 short 的上限没有概念，就很容易丢分。

二是引导你注意内存布局。short a[1010]占用的字节数是 2020 字节，如果用 int 则是 4040 字节，当年的竞赛环境内存并不宽裕，用 short 代表了一种“勤俭持家”的竞赛习惯。当然现在内存不值钱了，但这种类型意识在阅读他人代码时仍然重要。

3. 手工模拟：把 n=10 的每一步都摆到桌面上

3.1 建表过程全展演

阅读理解这类题，最笨也最有效的方法就是做小数据手工模拟。n=10 是最合适的样本，因为它足够小，可以一步步算完；又包含了质数（2、3、5、7）、合数（4、6、8、9、10）、平方数（4、9）等各种情况，能覆盖所有分支。

下面我把外层循环从 i=2 到 i=10 的完整过程列出来：

跑完这个表，a数组里的值是：

a[2]=2 a[3]=3 a[4]=2 a[5]=5 a[6]=2 a[7]=7 a[8]=2 a[9]=3 a[10]=2

注意看，这里a[8] = 2而不是4，因为 8 的最小质因子是 2；a[9] = 3，因为 9 的最小质因子是 3；a[10] = 2，因为 10 的最小质因子是 2。这个表一出来，后面所有题目都变成了“查表题”。

3.2 输出过程逐行还原

第二段循环负责输出。它的逻辑是：

for (int i = 2; i <= n; i++) { if (a[i] == i) cout << i << " "; else { int t = i; while (t > 1) { cout << a[t] << " "; t = t / a[t]; } } cout << endl; }

如果a[i] == i，说明 i 是质数，直接输出 i。如果a[i] != i，说明 i 是合数，需要沿着最小质因子表一步步拆解。比如 i=6 时，a[6]=2，输出 2，t 变成 3；然后 a[3]=3，输出 3，t 变成 1；循环结束，所以 6 输出为2 3。用刚才的 a 表，n=10 的完整输出是：

这里有一个非常容易踩的坑：题目问“输入的 n 等于 10 时，输出的第 5 行内容是什么”，很多考生直接去找数字 5 那行，看到 5 那行输出5，就选了错误答案。实际上，输出行号从 2 那一行开始算，第 5 行对应的是 i=6，输出内容是2 3。这种“第几行对应哪个 i”的对应关系，就是出题人专门设置的陷阱，手工模拟一遍就能完全避开。

4. 真题选项逐一推理：判断题和选择题的完整推导

4.1 判断题：n=100 时，a[101] 的值是 101 吗

答案：不是，这个判断是错的。

很多人看一眼觉得“a[i] = i 不是把每个数都赋成自己吗”，但问题在于，n=100 时外层循环for (int i = 2; i <= n; i++)最多执行到 i=100，根本轮不到给 a[101] 赋值。那内层循环会不会越界访问到 a[101]？也不会，因为内层循环条件j * i <= n，也就是j * i <= 100，所有乘积都不可能超过 100。

更严谨地说，a[101] 从初始化到程序结束都没有被写入过，它始终保持初值 0。所以当 n=100 时，a[101]的值是 0，不是 101。这道判断题考的是两层东西：一是循环边界意识，二是数组初始化的语义。short a[1010] = {0}会把整个数组全部初始化为 0，这个知识点在类数组和全局数组里尤其重要。

4.2 判断题：删除 if(i*i <= n)，输出是否不变

答案：不变，判断正确。

我在前面已经推导过，内层循环for (int j = i; j * i <= n; j++)的初始 j 等于 i，所以当i * i > n时，内层循环条件在第一次判断时就失败，循环体不会执行。也就是说，外层if (i * i <= n)是一个冗余判断，删掉它程序行为完全一样。

这种题目在竞赛阅读里很常见，考的是“你能不能看清循环条件的等价性”。推这类题最关键的一步，是把内层循环的“第一轮迭代”单独拿出来看：如果第一轮都进不去，那整个循环就是空的。这也提醒我们，读代码时不要被嵌套结构吓住，把“最内层循环的入口条件”单独抽出来分析，很多问题都会迎刃而解。

4.3 判断题：n=1000 时，程序不会访问到 a[1001] 吗

答案：不会访问到 a[1001]，这个判断是正确的（前提是题目问的是 1001 或更大下标）。

外层循环i <= n，访问的最大下标是 a[1000]。内层循环j * i <= n，在 n=1000 时，最大访问下标也是 a[1000]，因为所有乘积都被限制在 1000 以内。所以程序对 a 数组的访问范围是 2 到 1000，a[1001] 完全没被碰过。

这里可以再追问一句：如果 n 输入得很大呢？比如 n = 2000，而数组大小只有 1010，那么访问 a[1500] 时就会越界。C++ 数组越界是未定义行为，程序可能表现为输出错误结果、直接崩溃，还可能“碰巧”正常工作，这种不确定性正是竞赛题喜欢做文章的地方。所以读题时一定要先把“数组开多大”和“n 的取值范围”这两个信息刻在脑子里。

4.4 选择题：第 5 行输出到底是几

前面手工模拟已经给出了答案：n=10 时，第 5 行对应 i=6，输出是2 3。

这道选择题非常经典，因为它同时考察了两个能力：一是是否耐心做了小数据模拟，二是能否正确理解“第几行”的计数起点。很多考生凭直觉以为“第 5 行就是数字 5 的输出”，然后看到 5 是质数，输出一个 5，选了一个带 5 的选项，正好落入陷阱。

建议在草稿纸上无论如何都写一遍输出序列：2、3、2 2、5、2 3……写到第 5 个就能锁定答案。这个习惯花不了 30 秒，但在考场上价值极大。

4.5 选择题：每一行的输出是不是递增的

这道题需要分情况讨论。从算法本质看，程序输出的是“一个合数从小到大排列的质因数序列”，比如 8 输出2 2 2，9 输出3 3，12 输出2 2 3。这些序列一定是非递减的，也就是从左到右每个数都不小于前一个数。

为什么？因为每次 while 循环输出的是当前 t 的最小质因子a[t]，然后t变成t/a[t]。新的 t 的最小质因子，要么还是原来的最小质因子（如果这个质因子还没除完），要么比原来的最小质因子更大（因为更小的质因子已经全部除掉了）。所以序列天然不会下降。

但“递增”这个词有歧义。如果题目说的是“严格递增”（每次都比前一个大），那 4 输出2 2就直接反例了，答案应该是“错误”。如果题目说的是“从小到大排列”或“非递减”，那答案就是“正确”。考场上碰到这种表述，一定不要急着选，先看 4、8、9 这类输出里有重复数字的行，就能判断出题人用的是哪套定义。我印象里原题的正确答案方向是“每一行按非递减顺序输出”。

4.6 选择题：程序整体功能是什么

到了这一步，程序的功能已经非常清晰：对于 2 到 n 之间的每个整数，输出它的质因数分解结果，也就是把每个数写成若干质数相乘的形式，质因子按从小到大排列，每行一个数。

这里要注意区分几个容易混淆的说法：

• “输出 2 到 n 之间所有的质数”——不对，因为合数也会输出，只是被分解了。
• “判断 2 到 n 之间每个数是否为质数”——不对，程序没有输出 yes/no，而是直接输出质因子组合。
• “求每个数的最小质因子”——接近，但程序输出的是完整分解，不只是最小质因子。

一旦理解了a[i]的“最小质因子表”语义，这道功能题基本就是送分题。所以我说这题的命门是“读懂数组语义”，而不是对着代码猜。

5. 考场上这类题的“三板斧”：模拟、画表、找规律

5.1 第一板斧：先跑一个足够小的数据

遇到任何阅读程序题，只要时间允许，先挑一个小数据手工跑一遍。比如这道题，n=10 就是黄金样本。小数据的好处是：

• 计算量小，不会消耗太多考场时间。
• 能覆盖所有分支：质数、合数、平方数、连续重复质因子。
• 方便直接验证判断题里的边界结论，比如“a[101] 是否被访问”“第 5 行输出什么”。

我自己做题的习惯是，先在草稿纸上画一个 2 到 n 的表格，一行行填 a 数组的值。填完之后，输出部分等于查表，判断题的正确率会大幅提升。这个方法看起来笨，但比空想快得多，也稳得多。

5.2 第二板斧：给关键变量写“注释”

读别人代码时，最忌讳在脑子里把变量名当成抽象符号。看到一个a[i]，就要立刻在草稿纸旁边写一句：a[i] = i 的最小质因子。看到一个while (t > 1)，就要立刻知道它是在“沿着最小质因子表逐层分解 t”。这一步相当于给自己的大脑做注释，能把“读代码”变成“读设计意图”。

我在模拟这道题时，会特别标注a[i] == i的含义——它同时表达了“i 是质数”和“i 的最小质因子是它自己”两层意思。很多判断题的错误选项就是在利用这种“双重含义”做文章：选项说“a[101] 的值是 101”，实际上是在诱导你把“a[i] = i”和“所有 a 的下标都等于自身值”混为一谈。

5.3 第三板斧：边界和类型永远拉出来单独检查

判断题最爱埋伏的雷区就是边界和类型。每次读完循环，都要单独问自己三个问题：

• 循环下标的取值范围是什么？会不会访问到数组边界之外？
• 循环条件里的乘法会不会溢出？i * i在 n 很大时是否安全？
• 数组元素类型是 short、int 还是 long long？存的值是否会超出范围？

这道题里，short a[1010]就是典型的雷区。n=1000 时一切正常，但如果 n 超过 32767，a[i]=i 就可能溢出；n 超过 1010，访问就可能越界。出题人可以把这两个点包装成任何判断题，而你只要记住“short 上限 32767、数组长度 1010”这两个数字，就能把所有相关选项一举拿下。

5.4 考场时间分配的实战建议

初赛阅读程序题通常每道题下有 3 道判断、2 到 3 道选择，一共 5 到 6 个小题。很多选手在这道 20 多行的代码上耗了 15 分钟还犹豫不决。我的建议是：

先用 3 分钟做小数据模拟，把核心数组的值表画出来；再用 2 分钟逐题核对选项；如果某个判断题需要复杂的逻辑推理，先标记跳过，等其他题做完再回来推。阅读程序题拼的是“稳定拿分”，而不是“一口气解完”。让我反复强调一次：n=10 的完整模拟，就是这个题的定海神针。只要模拟表格在手，第 5 行输出、递增性、功能判断都能在 1 分钟内锁定。

6. 复盘这道题之后，还能顺手练什么

6.1 把它改成欧拉筛求最小质因子

这道题本质上是埃氏筛的变体。埃氏筛的时间复杂度是 O(n log log n)，已经足够快。但如果你对筛法感兴趣，可以试试把它改成欧拉筛（线性筛），让每个合数只被它的最小质因子筛掉一次：

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> minp(n + 1, 0); vector<int> primes; for (int i = 2; i <= n; i++) { if (minp[i] == 0) { minp[i] = i; primes.push_back(i); } for (int p : primes) { if (p > minp[i] || 1LL * i * p > n) break; minp[i * p] = p; } } for (int i = 2; i <= n; i++) { int t = i; while (t > 1) { cout << minp[t] << " "; t /= minp[t]; } cout << endl; } return 0; }

对比两种筛法你会发现，欧拉筛里p > minp[i]这个 break 条件，保证了每个合数只被最小质因子筛一次，线性的效率就是这么来的。而原题的埃氏筛变体虽然也能得到正确的最小质因子表，但某些合数会被多个质数尝试标记（比如 12 会被 2 和 3 都扫到），只是第二次会因为a[j*i] != 0而不再覆盖。理解这个差异，能帮你把“筛法家族”彻底串起来。

6.2 把 short 换成 int 的版本，输出会变吗

如果在草稿纸上把代码改一下，short a[1010]换成int a[1010]，在 n 不超过 1010 的前提下，输出完全一样。这说明 short 的选择不影响算法正确性，只影响存储范围和内存占用。但反过来说，如果 n 超过 32767，short 版本就可能输出错误结果，而 int 版本仍然正常。

这种“换个类型看看会不会变”的练习特别适合备考。它让你搞清楚哪些是算法的核心逻辑，哪些只是实现细节。竞赛阅读题经常在实现细节上设坑，而核心逻辑往往是一层窗户纸。

6.3 延伸：质因数分解在竞赛题里的常见用法

这道题输出了每个数的质因数分解，看似简单，背后却是数论题的“地基”。掌握了质因数分解，你可以顺手解决：

• 求一个数的正因子个数：n = p1^a1 * p2^a2 * ...，因子个数为 (a1+1)(a2+1)...。
• 求一个数的约数和：利用等比数列求和公式。
• 判断完全平方数：所有质因子的指数必须都是偶数。
• 最大公约数、最小公倍数的质因子解释：取各质因子指数的最小值或最大值。

这也是为什么我说这道“入门级”阅读题值得反复咀嚼——它不是一道孤立题，而是通往数论的一把钥匙。

最后再分享一个小技巧

我带学生刷初赛时，一直坚持一个规矩：阅读程序题不允许先看选项，必须先在草稿纸上写出自己对程序功能的一句话判断，再去看选项验证。这样做的好处是，你的思维不会被出题人的干扰项带偏，而是形成“先理解、后判断”的稳定路径。2022年这道 CSP-J1 第 1 题，如果你也按这个流程走，先画 n=10 的表，再写“程序在输出 2 到 n 的质因数分解”，那么所有小题都能稳稳拿下。

这道题真正的难点从来不是代码本身，而是很多选手习惯“看代码猜答案”，跳过了最关键的模拟和语义标注。把这套方法练成肌肉记忆，阅读程序题就不会再是你初赛的失分项。