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 是一个合数。举个例子n10 时程序运行结束后a[6] 2、a[9] 3、a[7] 7。6 的最小质因子是 29 的最小质因子是 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 是一个合数。此时程序跳过它不进入内层循环。这其实就是埃氏筛的精髓只有质数才有资格作为“筛子”去标记它的倍数。为什么合数不能作为筛子因为合数的最小质因子一定比它本身小既然它已经被更小的质数标记过那么它的所有倍数也一定早就被那个更小的质数标记过了重复标记没有任何意义。比如 i6 时a[6]26 是合数而 6 的倍数比如 12、18 等早在 i2 或 i3 的时候就已经被处理过甚至会被标记上最小质因子所以跳过 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 不超过 32767a[i]里存的最小质因子值就不会超范围用 short 完全够。但如果哪天 n 输入得很大比如 n 50000那么当 i 49999 是质数时a[49999] 4999949999 已经超过了 short 的上限 32767会发生溢出存进去的值就不是 49999 了。不过在原题的典型数据范围n 1000 或 n 10000里short 是安全的。那为什么出题人要用 short我觉得有两个考虑一是考察选手对类型范围的敏感度。判断题里完全可能埋伏“如果 n 大于 32767程序可能出错”这种选项如果你对 short 的上限没有概念就很容易丢分。二是引导你注意内存布局。short a[1010]占用的字节数是 2020 字节如果用 int 则是 4040 字节当年的竞赛环境内存并不宽裕用 short 代表了一种“勤俭持家”的竞赛习惯。当然现在内存不值钱了但这种类型意识在阅读他人代码时仍然重要。3. 手工模拟把 n10 的每一步都摆到桌面上3.1 建表过程全展演阅读理解这类题最笨也最有效的方法就是做小数据手工模拟。n10 是最合适的样本因为它足够小可以一步步算完又包含了质数2、3、5、7、合数4、6、8、9、10、平方数4、9等各种情况能覆盖所有分支。下面我把外层循环从 i2 到 i10 的完整过程列出来ia[i] 初始值是否进入 if(a[i]0)操作内层循环执行情况20是a[2]2j2: a[4]2j3: a[6]2j4: a[8]2j5: a[10]230是a[3]3j3: a[9]3j4 时 1210 停止42否跳过无50是a[5]5j5 时 2510循环不执行62否跳过无70是a[7]7j7 时 4910循环不执行82否跳过无93否跳过无102否跳过无跑完这个表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 的最小质因子是 2a[9] 3因为 9 的最小质因子是 3a[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 是合数需要沿着最小质因子表一步步拆解。比如 i6 时a[6]2输出 2t 变成 3然后 a[3]3输出 3t 变成 1循环结束所以 6 输出为2 3。用刚才的 a 表n10 的完整输出是i输出内容223342 25562 37782 2 293 3102 5这里有一个非常容易踩的坑题目问“输入的 n 等于 10 时输出的第 5 行内容是什么”很多考生直接去找数字 5 那行看到 5 那行输出5就选了错误答案。实际上输出行号从 2 那一行开始算第 5 行对应的是 i6输出内容是2 3。这种“第几行对应哪个 i”的对应关系就是出题人专门设置的陷阱手工模拟一遍就能完全避开。4. 真题选项逐一推理判断题和选择题的完整推导4.1 判断题n100 时a[101] 的值是 101 吗答案不是这个判断是错的。很多人看一眼觉得“a[i] i 不是把每个数都赋成自己吗”但问题在于n100 时外层循环for (int i 2; i n; i)最多执行到 i100根本轮不到给 a[101] 赋值。那内层循环会不会越界访问到 a[101]也不会因为内层循环条件j * i n也就是j * i 100所有乘积都不可能超过 100。更严谨地说a[101] 从初始化到程序结束都没有被写入过它始终保持初值 0。所以当 n100 时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 判断题n1000 时程序不会访问到 a[1001] 吗答案不会访问到 a[1001]这个判断是正确的前提是题目问的是 1001 或更大下标。外层循环i n访问的最大下标是 a[1000]。内层循环j * i n在 n1000 时最大访问下标也是 a[1000]因为所有乘积都被限制在 1000 以内。所以程序对 a 数组的访问范围是 2 到 1000a[1001] 完全没被碰过。这里可以再追问一句如果 n 输入得很大呢比如 n 2000而数组大小只有 1010那么访问 a[1500] 时就会越界。C 数组越界是未定义行为程序可能表现为输出错误结果、直接崩溃还可能“碰巧”正常工作这种不确定性正是竞赛题喜欢做文章的地方。所以读题时一定要先把“数组开多大”和“n 的取值范围”这两个信息刻在脑子里。4.4 选择题第 5 行输出到底是几前面手工模拟已经给出了答案n10 时第 5 行对应 i6输出是2 3。这道选择题非常经典因为它同时考察了两个能力一是是否耐心做了小数据模拟二是能否正确理解“第几行”的计数起点。很多考生凭直觉以为“第 5 行就是数字 5 的输出”然后看到 5 是质数输出一个 5选了一个带 5 的选项正好落入陷阱。建议在草稿纸上无论如何都写一遍输出序列2、3、2 2、5、2 3……写到第 5 个就能锁定答案。这个习惯花不了 30 秒但在考场上价值极大。4.5 选择题每一行的输出是不是递增的这道题需要分情况讨论。从算法本质看程序输出的是“一个合数从小到大排列的质因数序列”比如 8 输出2 2 29 输出3 312 输出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 第一板斧先跑一个足够小的数据遇到任何阅读程序题只要时间允许先挑一个小数据手工跑一遍。比如这道题n10 就是黄金样本。小数据的好处是计算量小不会消耗太多考场时间。能覆盖所有分支质数、合数、平方数、连续重复质因子。方便直接验证判断题里的边界结论比如“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]就是典型的雷区。n1000 时一切正常但如果 n 超过 32767a[i]i 就可能溢出n 超过 1010访问就可能越界。出题人可以把这两个点包装成任何判断题而你只要记住“short 上限 32767、数组长度 1010”这两个数字就能把所有相关选项一举拿下。5.4 考场时间分配的实战建议初赛阅读程序题通常每道题下有 3 道判断、2 到 3 道选择一共 5 到 6 个小题。很多选手在这道 20 多行的代码上耗了 15 分钟还犹豫不决。我的建议是先用 3 分钟做小数据模拟把核心数组的值表画出来再用 2 分钟逐题核对选项如果某个判断题需要复杂的逻辑推理先标记跳过等其他题做完再回来推。阅读程序题拼的是“稳定拿分”而不是“一口气解完”。让我反复强调一次n10 的完整模拟就是这个题的定海神针。只要模拟表格在手第 5 行输出、递增性、功能判断都能在 1 分钟内锁定。6. 复盘这道题之后还能顺手练什么6.1 把它改成欧拉筛求最小质因子这道题本质上是埃氏筛的变体。埃氏筛的时间复杂度是 O(n log log n)已经足够快。但如果你对筛法感兴趣可以试试把它改成欧拉筛线性筛让每个合数只被它的最小质因子筛掉一次#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint minp(n 1, 0); vectorint 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 超过 32767short 版本就可能输出错误结果而 int 版本仍然正常。这种“换个类型看看会不会变”的练习特别适合备考。它让你搞清楚哪些是算法的核心逻辑哪些只是实现细节。竞赛阅读题经常在实现细节上设坑而核心逻辑往往是一层窗户纸。6.3 延伸质因数分解在竞赛题里的常见用法这道题输出了每个数的质因数分解看似简单背后却是数论题的“地基”。掌握了质因数分解你可以顺手解决求一个数的正因子个数n p1^a1 * p2^a2 * ...因子个数为 (a11)(a21)...。求一个数的约数和利用等比数列求和公式。判断完全平方数所有质因子的指数必须都是偶数。最大公约数、最小公倍数的质因子解释取各质因子指数的最小值或最大值。这也是为什么我说这道“入门级”阅读题值得反复咀嚼——它不是一道孤立题而是通往数论的一把钥匙。最后再分享一个小技巧我带学生刷初赛时一直坚持一个规矩阅读程序题不允许先看选项必须先在草稿纸上写出自己对程序功能的一句话判断再去看选项验证。这样做的好处是你的思维不会被出题人的干扰项带偏而是形成“先理解、后判断”的稳定路径。2022年这道 CSP-J1 第 1 题如果你也按这个流程走先画 n10 的表再写“程序在输出 2 到 n 的质因数分解”那么所有小题都能稳稳拿下。这道题真正的难点从来不是代码本身而是很多选手习惯“看代码猜答案”跳过了最关键的模拟和语义标注。把这套方法练成肌肉记忆阅读程序题就不会再是你初赛的失分项。