备考PAT乙级的时候我在“数素数”这道题上栽过跟头。题目本身看着人畜无害给定M和N输出第M个到第N个素数每10个一行。我原来以为这就是个循环判断素数的小题结果提交之后才意识到它同时考了素数生成效率、数组上界估算和输出格式细节是一道典型的“看着简单、写起来全是坑”的题目。我把自己的思考和踩坑过程完整写下来希望能帮正在刷题的人少走弯路。1. 题目拆解PAT 1013到底在考什么1.1 先读懂题面“第M个素数”是什么意思题目里定义(P_i)表示第(i)个素数也就是说(P_12)(P_23)(P_35)以此类推。输入是两个正整数(M)和(N)满足(1 \le M \le N \le 10000)要求输出(P_M)到(P_N)的所有素数。我第一次做的时候没仔细看“第几个”这个概念直接写了一个从2开始往上找素数的循环想着找到M到N之间的素数就输出。这个理解错了一点点题目不是要范围在M和N之间的素数而是要索引在M和N之间的素数。举例来说如果输入是“2 4”输出应该是第2个、第3个、第4个素数也就是3、5、7而不是从2到4之间的素数2和3。搞清楚这一点后面才不会白写。这道题的输入范围给到了10000意味着最多要输出 (P_{10000})。我一开始也在思考到底要不要事先估算第10000个素数有多大。这是这道题最容易被忽略的一个点如果不知道这个上限你连循环该到哪里停止都说不清楚。稍微查一下或者自己跑一遍就能知道第10000个素数是104729超过十万了。所以任何“从2循环到100000找素数”的写法其实都是不够稳的因为100000以内根本装不下第10000个素数。1.2 这道题的三个隐藏考点排在第一的肯定是素数判断这个方法本身这部分已经有很多人讲过核心无非是试除法还是筛法。但除了素数判断这道题还有两个更容易被人忽略的考点。第二点就是运行时间限制。PAT乙级题目的时间限制一般是200ms或者400ms具体到1013这道题如果用最朴素的“从2到n逐个试除”来判断每个数再加上你根本不知道要试到什么时候为止那在N10000这种数据范围下是有可能超时的。我实测过纯靠试除法从2一路验到104729在部分老机器上会卡在时间边缘。这个问题看起来很轻微但恰恰是很多人在测试点3、4超时的原因。第三个隐藏考点是输出格式。“每10个数字占1行其间以空格分隔但行末不得有多余空格”这句话就是典型的OJ判题陷阱。如果你每输出一个数字后面都跟一个空格或者每满10个数字后换行但没有处理好行尾空格那结果就是格式错误Presentation ErrorPE在PAT里同样算错。这道题在输出上设置的陷阱几乎和素数判断本身一样重要。2. 核心原理素数的判断与生成2.1 试除法最直白的思路但需要注意细节判断一个正整数(n)是不是素数最基础的办法就是从2试到(\sqrt{n})看有没有能整除的数。为什么只需要试到(\sqrt{n})因为如果一个数(n)能被某个整数(d)整除那么(\frac{n}{d})也一定整除(n)而这两个因子中至少有一个不大于(\sqrt{n})。换句话说如果在([2, \sqrt{n}])这个区间里找不到因子那在((\sqrt{n}, n-1])这个区间里也一定找不到。很多人写试除法会随手写成for (int i 2; i n; i)这在小数字下没有感觉但数字一大效率就很差。正确的写法应该是for (int i 2; i * i n; i)或者用sqrt(n)作为边界。我建议用i * i n因为这样可以避免调用sqrt()函数带来的浮点精度问题也省掉引入math.h的麻烦。需要注意的是i * i在n特别大的时候可能溢出但在这道题涉及的范围内十万级完全不用担心。还有一个我自己容易忽略的问题1不是素数2是素数。判断函数开头必须处理n 2的情况否则你会在统计第1个素数时得到错误的答案。很多初学C语言的代码里isPrime(1)会返回1这会直接导致第一个素数被误判。2.2 埃氏筛法一次生成一张素数表省事又高效如果你需要频繁判断很多数是不是素数或者像这道题一样需要生成一大段素数序列那用试除法一个个判断就很吃亏。这时候埃拉托斯特尼筛法简称埃氏筛Sieve of Eratosthenes就非常合适。它的思路有点像我们小学时候做的“数数划掉”游戏先假设所有数都是素数然后从2开始把每个素数的倍数全部标记为合数剩下的就是素数。具体做法是开一个布尔数组初始全部置为1表示素数然后把isPrime[0]和isPrime[1]置为0。接下来从2开始遍历如果当前数字是素数就把它的所有倍数标记成0。这里有一个优化细节内层循环可以从i * i开始而不是从2 * i开始。为什么可以这样因为对于(i)来说小于(i^2)的倍数比如(2i, 3i, 4i, \dots, (i-1)i)在之前枚举更小的素数时已经被标记过了。比如枚举2时把6标记掉枚举3时就不用再从6开始直接从9开始就行。这样能省掉大量重复标记。埃氏筛的时间复杂度是(O(n \log \log n))空间复杂度是(O(n))。在本题目给定的数据范围下它比试除法快得多而且代码量也没增加多少。我个人的习惯是凡是遇到要输出一长串素数或者反复判断素数的题优先用筛法因为它在时间上几乎没有风险。3. 实操方案从思路到代码两种写法都给你摆出来3.1 筛法版本C语言完整实现与逐段拆解先直接上我最终提交的C语言代码这个版本在PAT上是能一次AC的#include stdio.h #define MAX 110000 int isPrime[MAX]; int main() { int M, N; int count 0; int outCount 0; scanf(%d %d, M, N); // 初始化默认全部是素数 for (int i 0; i MAX; i) { isPrime[i] 1; } isPrime[0] isPrime[1] 0; // 埃氏筛核心 for (int i 2; i * i MAX; i) { if (isPrime[i]) { for (int j i * i; j MAX; j i) { isPrime[j] 0; } } } // 遍历所有数字统计素数个数并输出第M到第N个 for (int i 2; i MAX count N; i) { if (isPrime[i]) { count; if (count M) { if (outCount 0 outCount % 10 ! 0) { printf( ); } printf(%d, i); outCount; if (outCount % 10 0) { printf(\n); } } } } // 如果最后一行没满10个补一个换行可选但建议 if (outCount % 10 ! 0) { printf(\n); } return 0; }我来说说几个关键点。首先是MAX的取值。我之前提过第10000个素数是104729所以MAX至少要开到104730。我习惯直接开110000给一点冗余省得边界出问题。在C语言里直接#define MAX 110000数组大小是110000 * sizeof(int)如果是4字节的int大约是440KB完全在内存限制之内。这里不需要精打细算宁可开大一点也不要开小了。然后是埃氏筛内层循环的起点j i * i这个我在前面解释过原理。还有一个细节外层循环只要i * i MAX就够了因为如果i大于sqrt(MAX)那i * i已经超出数组范围标记也就没有意义了。最后是输出逻辑。我用outCount记录已经输出多少个数字outCount % 10 ! 0表示当前不是该行的第一个数字此时输出一个空格再输出数字本身。当outCount % 10 0时换行。这样输出格式就能保证每行10个数字行尾没有多余空格行首也没有多余空格。3.2 试除法版本适合理解但实测容易踩时间线如果你暂时不想用筛法也可以用试除法写出一个能AC的版本。先看代码#include stdio.h int isPrime(int n) { if (n 2) { return 0; } for (int i 2; i * i n; i) { if (n % i 0) { return 0; } } return 1; } int main() { int M, N; int count 0; int outCount 0; scanf(%d %d, M, N); for (int i 2; ; i) { if (isPrime(i)) { count; if (count M) { if (outCount 0 outCount % 10 ! 0) { printf( ); } printf(%d, i); outCount; if (outCount % 10 0) { printf(\n); } if (outCount N - M 1) { break; } } } } if (outCount % 10 ! 0) { printf(\n); } return 0; }这个版本的好处是代码逻辑非常直观从2开始一个个判断找到第M个就开始输出直到输出完(N-M1)个就结束。你不用提前知道第10000个素数是多少因为循环是for (int i 2; ; i)无限进行的直到找到第N个素数才break。但坏处也很明显isPrime函数会对大量数字重复计算。虽然每个数字最多被算一次但算到104729附近的时候即使做了i * i n的优化总耗时也会比筛法高不少。我在自己的电脑上测试当N10000时试除法版本大约需要几十毫秒到上百毫秒取决于机器性能。在OJ上如果服务器负载高一些这个版本就有超时风险。我的建议是如果你想加深理解可以用试除法写一遍并本地跑通但真正提交的时候还是用筛法更稳妥。3.3 一个容易被忽视的边界第10000个素数到底有多大这个知识点太重要了我必须单独拿出来说。很多人写筛法时数组范围是随手写的#define MAX 100000理由是题目输入N最大是10000感觉10万应该够用。但是第10000个素数根本不是小于100000的某个数而是104729。我用一个简单脚本验过100000以内的素数个数其实是9592个根本到不了第10000个。如果你把数组开成100000程序在输出第9592个素数之后继续往下找但数组下标超过99999要么访问越界要么在循环条件上提前终止最终要么段错误要么漏输出反正就是不能AC。这道题让我吃了这个亏之后养成了“先估算答案规模再开数组”的习惯。如果实在不知道第10000个素数有多大最简单的办法就是用试除法先跑一遍把第10000个素数打印出来看然后再定数组大小。4. 格式输出的细节一半的坑都在这里4.1 “每10个一行、行末无空格”到底怎么实现我先说说最常见的一种错误写法每输出一个素数就printf(%d , i);每满10个就printf(\n);。这样写的问题在于每个数字后面都带一个空格而题目要求“行末不得有多余空格”。如果OJ是严格文本比对这种输出会被判成格式错误。正确的做法是在打印下一个数字之前判断“是否需要打印空格”而不是在打印完数字之后统一补空格。我上面给出的代码用的是if (outCount 0 outCount % 10 ! 0) printf( );意思是只要不是这一行的第一个数字就在数字前面补一个空格。这样每行最后一个数字后面是绝对没有空格的因为下一个数字换行之后outCount % 10就变成0了不会再补空格。另一个需要注意的地方是最后一个数字如果是该行的第10个printf(\n)已经被执行了但如果最后一个数字不是第10个循环直接break末尾就没有换行。我在代码里加了最后一行if (outCount % 10 ! 0) printf(\n);统一在最后补一个换行。这样输出文件的最后一定以换行结尾更符合题目规范。大多数OJ其实不强制要求最后必须有换行但加上总没坏处。4.2 输出时用索引计数别用M、N直接控制我在多次刷题中发现输出环节最容易弄错的不是空格而是计数混乱。比如有人会用双重循环外层遍历素数内层控制输出个数结果边界判断写得绕来绕去。我推荐的做法是用count记录当前遍历到的素数是第几个素数用outCount记录已经输出几个素数。count从0开始每遇到一个素数就count当count落在[M, N]范围内时执行输出outCount只在输出时递增当它达到N - M 1时说明所有需要输出的素数都已经输出完毕可以结束。这种思路把“找素数”和“输出”两个逻辑拆开不容易乱。还有人喜欢直接在循环里判断if (count M count N)也可以但要注意当count N时及时退出循环否则白白浪费计算资源。我上面的代码用的是主循环条件count N和内部的break双保险实际跑起来不会有问题。4.3 关于剩余换行的几个细节验证我在本地测试的时候特意用了几组数据来验证输出。比如输入5 27输出结果应该是从第5个素数11到第27个素数103一共23个数字前两行各10个第三行3个。正确输出是11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103我拿这个结果仔细对照过代码的行为第一行从11开始outCount从0递增到9所以第一个输出11前没有空格第二个13前有空格一直到43被输出时outCount是9满足outCount % 10 0于是换行。第二行同理。第三行输出103后outCount变成23不是10的倍数循环结束最后由if (outCount % 10 ! 0) printf(\n)补上换行。整体格式没有问题。还有一个更极端的测试输入1 10输出2到29正好满一行最后outCount % 10 0末尾换行已经通过printf(\n)输出最后的补换行就不会触发。这个细节说明两个换行机制互不冲突可以放心用。5. 常见问题与踩坑实录5.1 测试点总是超时先检查是不是用了双重试除PAT的OJ测试点不会告诉你具体哪里超时只会给你一个红色的“运行超时”或者“部分正确”。我最初提交用的是一个简化版的试除法每个数都从2试到它本身结果N一接近10000运行时间直接爆掉。后来我优化成从2试到sqrt(n)虽然好了一些但还是不够稳。最终换成埃氏筛后测试点的运行时间降到了个位数毫秒这才放心。我的建议是如果你已经写了i * i n的试除法还在超时那可以试试筛法。这道题N10000筛110000范围内的素数是非常快的不需要任何花哨优化就能通过。5.2 数组越界和“段错误”问题有些同学的代码在本地跑小数据都没问题但一提交就“段错误”或者“运行时错误”。最常见原因就是数组开到100000而第10000个素数却在104729。当程序判断第10000个素数时循环变量i已经跑到104729如果数组长度不够isPrime[i]就会越界访问轻则读出垃圾值重则直接段错误。顺带一提C语言里这种越界有时候不会立即崩溃可能只是地址刚好落在可读的虚拟内存区域导致程序继续运行输出一些莫名其妙的结果。这种“不报错但结果错误”的越界是最难排查的。我用-fsanitizeaddress编译运行过才能准确看到到底是哪一行越界了。大家可以本地开这个编译选项试试比如gcc -fsanitizeaddress main.c -o main能快速定位这类问题。5.3 输出格式错误的几种经典表现我在PAT上遇到过的“答案错误”背后其实有相当一部分是输出格式问题。下面这个表列举了几种常见症状和对应原因我把它当作刷题时的自查清单症状可能原因解决办法每行行尾都多一个空格简单用printf(%d , i)输出没有处理行尾改成在数字前补空格所有数字挤在一行里忘了在outCount % 10 0时换行加换行判断行尾和行首都多余空格空格逻辑和换行逻辑冲突统一用outCount控制行首不补、行中补、满10换行最后一行后面多一个空行最后补换行时没有判断是否已经换过加if (outCount % 10 ! 0)判断我自己就犯过第一类错误当时还觉得奇怪“不是每10个一行吗我每个数字后面都有空格满足了‘空格分隔’啊。”后来我才想明白OJ对输出的判断是逐字符对比的行尾多了一个空格就是错误。刷题这件事有几个特点规范严格、结果导向平时写代码觉得“差不多”的地方在OJ这里就是“差很多”。5.4 关于素数生成上限的快速自查方法如果你不确定自己的数组上限够不够有一个很简单的估算方法素数定理告诉我们小于(x)的素数大约有(\frac{x}{\ln x})个。反过来要求第10000个素数可以大致解方程(\frac{x}{\ln x} \approx 10000)得到的(x)大概在104000附近。这和104729的实际值很接近。我觉得用这个办法来定上限非常实用做题时心里有个数就不用瞎猜了。当然最准的还是直接跑一遍但做笔试题或者OJ题没时间去跑的时候素数定理的估算完全可以帮上忙。6. 最后再说点个人的做题体会我在PAT乙级刷题过程中1013这道题反复做了三遍。第一遍用试除法换行格式错了第二遍用筛法数组开小了一点点第三遍才把所有细节全部处理干净一次AC。回头来看这道题其实是在提醒我算法题能不能通过不只要看“会不会”还要看“边界条件能不能想全”。素数判断谁都会写但第10000个素数有多大、行末空格怎么处理、数组开多少这些细节才是拉开差距的地方。还有一个小经验我在本地测试时通常会把输出重定向到文件里然后用diff命令和标准答案做比对。比如标准结果文件叫ans.txt我程序输出叫out.txt执行diff -w out.txt ans.txt如果有差异会直接显示出来。这个习惯帮我节省了大量时间因为肉眼在一大串数字里找空格错误实在太折磨人了。如果你也在刷PAT我建议你也试试这个做法。