PAT乙级1013这道题我印象太深了。当年刷PAT的时候我在它身上栽过一次“格式错误”原因是最后一个数字后面多了个空格。题名叫“数素数”一眼看去就是输出一堆素数但实际上手才发现坑全藏在细节里第m个到第n个这种“下标定位”的表述、每行10个的排版、行末不能有空格的要求——每一项都不难但组合在一起就能筛掉一大批粗心的人。这道题值得拿出来单独写一篇是因为它特别适合用来检验你的基本功素数判断怎么写、循环边界怎么卡、输出格式怎么控。不管你是正在备考PAT的考生还是刚学C语言想找题练手的初学者把这道题吃透后面遇到类似的“数学题格式输出”组合就不会再慌。这篇就按我自己的做题思路来复盘从题目拆解、算法选型到代码实现、踩坑记录全程干货。1. 题目拆解与整体思路1.1 题目到底在考什么先把题面说清楚。PAT乙级1013“数素数”输入两个正整数M和N1≤M≤N≤10^4要求输出从第M个素数到第N个素数的所有素数。这里的“第几个”是下标概念第1个素数是2第2个素数是3第3个素数是5以此类推。不是让你输出数值范围[M, N]里的素数而是输出素数序列中排名第M到第N的那一段。举个例子如果输入1 10输出的就是前10个素数2、3、5、7、11、13、17、19、23、29。如果输入10 20输出的是第10个到第20个素数也就是29到71之间那11个数。这道题的考点有三层素数判断本身这是核心算法必须写对。边界处理M和N可以相等M可以是1N最大到10000循环什么时候停要算清楚。输出格式每行最多10个数字每个数字占5位宽度行末不能有多余空格最后一行要有换行。前两点属于“做对”第三点属于“得分”。PAT对输出格式的要求极其严格格式错了就是0分哪怕算法全对也没用。所以我会把格式控制单独拿出来重点讲。1.2 两条解题路线的选择面对这道题做题思路分两个流派逐个判断从2开始往上遍历每个整数用isPrime()判断是不是素数是素数就计数一直数到第N个素数为止途中把第M到第N个输出。批量筛取用埃氏筛Eratosthenes筛法一次性把范围内所有合数标记出来剩下的就是素数表然后直接从表里取第M到第N个。两种思路都能通过这道题。区别在于逐个判断写起来更直白适合刚学算法的人筛法代码稍长但背后是“预处理换时间”的经典思想理解它对以后做更大数据量的题有帮助。我对这道题的建议是两种都写一遍。先写逐个判断版本确保逻辑清晰再写筛法版本感受一下两种思路的效率差。我自己刷题时就是先写了试除版AC之后又写了筛法版对比下来对“素数密度”这个概念理解深了不少。下面两章分别把这两种写法的原理和细节掰开讲。2. 素数判断的核心原理与细节2.1 试除法从最朴素写法到优化写法试除法是判断素数最基础的方法对于一个大于1的自然数n依次尝试用2到n-1之间的每个整数去除n如果存在能整除的n就是合数一个都没有n就是素数。最朴素的写法长这样int isPrime(int x) { if (x 2) return 0; for (int i 2; i x; i) { if (x % i 0) return 0; } return 1; }这写法没错但效率太低。对于x104729这种数要循环10万次而我们在题目中最多要判断到第10000个素数累计循环次数相当可观。虽然PAT的测试数据未必能卡到你超时但作为刷题的人不该满足于“刚好能过”的写法。优化的方向就一句话把循环上界从x降下来。你不需要试验x-1到2的所有数只需要试验2到√x之间的整数。原因我在下一节详细解释。优化之后再叠加一个常用技巧先判断偶数。除了2以外所有偶数都不是素数所以可以先排除x % 2 0的情况然后从3开始每次步进2只检查奇数。这样循环次数又砍一半。int isPrime(int x) { if (x 2) return 0; if (x 2) return 1; if (x % 2 0) return 0; for (int i 3; i * i x; i 2) { if (x % i 0) return 0; } return 1; }这里有个细节循环条件我用的是i * i x而不是i sqrt(x)。原因是sqrt()是浮点运算存在精度误差而且每次循环都调用sqrt()本身也有开销。i * i是整数乘法在这个题目里x最大10万多i*i远不到int上限完全可行。如果想再极致一点还有基于“素数只能表示为6k±1”的6倍法优化。但说实话对1013这道题判断到√x加步进2的版本已经绰绰有余再优化属于杀鸡用牛刀。我平时做笔试写代码追求的是“好写、好读、不易错”优先所以推荐大家先把上面这个版本吃透。2.2 为什么只需判断到平方根刚学编程的人通常会有个疑问凭什么判断到√x就够了万一合数的一个因子比√x大呢这个疑问的解法是想清楚一件事对于一个合数x如果它存在一个大于√x的因子a那它必然存在一个小于√x的因子b因为x a × b而a √x时b x / a必然小于√x。既然在2到√x之间已经能找到一个b整除x试除到√x时早就该返回0了根本不需要去管那个大于√x的a。我用生活里的例子类比一下你要判断36是不是素数因数有1、2、3、4、6、6、9、12、18、36。如果你从2开始往试试到4就已经发现36能被4整除直接在中间就确认它是合数了。9和12这些比6大的因子根本轮不到上场。所以试除范围取到√x而不是x/2或x-1是数学上严格成立的上界。用这个结论再看上面的代码循环到i * i x为止对x104729只需要试到323循环次数大约161次只试奇数。相比朴素的10万次循环效率提升了大约600倍。氧化一下概念整个判断1万个素数的总试除次数大约是多少第10000个素数是104729每个数平均尝试160多次总共约160万次模运算。这个量级在现代CPU上就是毫秒级的事。所以试除法在这道题里完全够用。2.3 边界条件与奇偶性优化的取舍写isPrime函数时最容易出错的就是边界值。我总结出三个必查的点第一x小于2直接返回0。特别要注意1不是素数这是新手最容易踩的地方。有些写法是“只要从2试到x-1没找到因子就返回1”那对x1就会错误地输出1是素数。第二x等于2单独处理。2是唯一的偶素数如果不先处理x % 2 0的情况2会被误判为合数。所以代码里我会先判断x 2返回1再判断x % 2 0返回0顺序不能反。第三循环起点写成3而不是2。既然已经把偶数排除了再从2开始试就显得多余。步长用2而不是保证只查3、5、7、9、11这样的奇数。这三个点合起来就是上面那段isPrime代码的完整逻辑。我建议大家在草稿纸上手写几遍这个函数把每一种情况都过一遍x1返回0x2返回1x4返回0x9返回0x11返回1。全部正确后再开始写主函数基础函数不写稳后面全是返工。3. 埃氏筛法大范围素数的高效解法3.1 从“逐个验证”到“批量标记”的思路转换试除法的思路是“一个一个验证”埃氏筛法的思路则反过来预先开一个大数组从2开始找到第一个没被标记的数i它一定是素数然后把i的2倍、3倍、4倍……全部标记为合数。这样一轮扫下来所有合数都被标记剩下没被标记的全是素数。埃氏筛的精髓在于它的时间复杂度约是O(n log log n)对于“一次性求出10万以内所有素数”这种需求效率比反复试除高得多。如果你需要频繁判断区间内的素数筛法把结果预处理成素数表后面就是O(1)查询。但要注意筛法的内存开销是数组大小。对于这道题第10000个素数是104729你至少要把数组开到104729以上。这个范围放到现代编译器里也就是一个int数组几百KB的事完全没压力。3.2 埃氏筛的代码实现细节埃氏筛的标准写法#include stdio.h #define MAX 110000 int isComposite[MAX]; int main() { int m, n; scanf(%d%d, m, n); for (int i 2; i * i MAX; i) { if (!isComposite[i]) { for (int j i * i; j MAX; j i) { isComposite[j] 1; } } } int count 0; for (int i 2; i MAX; i) { if (!isComposite[i]) { count; if (count m count n) { printf(%5d, i); if ((count - m 1) % 10 0) printf(\n); } if (count n) break; } } if ((n - m 1) % 10 ! 0) printf(\n); return 0; }这里有几个实现细节值得说内层循环的起点用i * i而不是i * 2。因为i * 2、i * 3这些数在更小的素数处理时已经被标记过了。举个例子i5时5×210早在i2时就被标记了5×315早在i3时就被标记了。从i×i开始标记既避免重复又减少无用操作。这是一点小优化但对理解算法本身很有帮助。数组isComposite[i]表示“i是不是合数”。初始化时全0代表先假设所有数都是素数。真正的筛法代码里不需要单独把0和1标记为合数因为遍历的时候从2开始0和1根本不会被访问。但在其他应用场景里如果你要查isPrime[0]或isPrime[1]就得手动处理。外层循环的终止条件是i * i MAX而不是i MAX。因为如果i √MAX那么i的合数倍数中至少存在一个小于i的因子那些数在更早的轮次里已经被标记过了。比如MAX110000i400时400×2800早就被2标记了。继续循环只是在重复劳动。3.3 第10000个素数104729数组开多大才够筛法有个避不开的问题数组上限得提前定好。开小了筛不出第n个素数开大了浪费内存——不过在本题范围内浪费一点也无所谓。我代码里写的是#define MAX 110000为什么是这个数因为第10000个素数是104729。这是一个数学上已知的结果常见于素数表。所以数组开到110000比104729大出差不多5000的余量保证第10000个素数一定落在数组范围内。如果你不想背104729这个数字也有懒办法先开一个10万的数组做筛法如果统计出来的素数数量不足n就扩大到20万再筛一次。但这样代码写起来复杂还得重复初始化。我更推荐的做法是查一下素数表这道题里记住104729并不难。写到这里顺便提一句PAT的1013题试除法完全能过筛法属于“更好看”的解法。但筛法的思路在你以后做“区间素数”“素数个数统计”这类题目时会反复用到所以我建议两种写法都练熟。4. 实操过程与完整代码实现4.1 搭框架输入、计数、输出格式控制不管用哪种算法主函数的框架是一样的读入m和n。从2开始逐个检查或查表得到素数。维护一个计数器count表示当前已经找到第几个素数。当count落在[m, n]区间内时输出当前素数。按格式要求控制换行和宽度。这里最容易被忽略的是输出格式。题目要求每个数字占5位宽度用printf(%5d, i)就能实现。如果你的平台上的题目描述是“数字之间以空格分隔”而不是“占5位宽度”那就去掉%5d改用普通输出。我印象中PAT官方原题是要求占5位宽度的但不同题库的改编版可能有出入考试时一定以题面为准。行末不能有多余空格这句话是PAT的经典陷阱。很多人用“先输出数字再判断是不是最后一个最后一个不输出空格”的方式来控制这样也能过但我个人更喜欢下面这种写法每次都输出%5d然后判断“这一行是否已经输出满10个”。满10个就换行这个数字自然就是行末最后一个没有多余空格。空格的本质是%5d格式符里的宽度/前导空格并不是手动加的空格所以不存在“行末多空格”的问题。4.2 试除法版本完整代码与逐段解析完整代码我已经在2.1小节给过isPrime函数了这里给完整的主程序#include stdio.h int isPrime(int x) { if (x 2) return 0; if (x 2) return 1; if (x % 2 0) return 0; for (int i 3; i * i x; i 2) { if (x % i 0) return 0; } return 1; } int main() { int m, n; scanf(%d%d, m, n); int count 0; int printed 0; int x 2; while (1) { if (isPrime(x)) { count; if (count m count n) { printed; printf(%5d, x); if (printed % 10 0) printf(\n); } if (count n) break; } x; } if (printed % 10 ! 0) printf(\n); return 0; }逐段解释一下count统计找到的素数个数printed统计已经输出的数字个数。while(1)里对x逐个调用isPrime判断。找到素数后count自增。当count到达m时开始输出直到count超过n时退出循环。输出时printed自增每满10个就换行。这样第10、20、30个数字后面正好是一个换行。循环结束后如果printed不是10的倍数说明最后一行没满需要补一个换行。如果printed正好是10的倍数最后一行已经在循环里换过行了不能再补。这个版本的变量设计有一个小巧思printed % 10直接控制换行不用额外关心“这是行内第几个”的位置。我一开始写这题时用的是“行内计数器”每输出一个就cntInLine满10清零后来发现直接对printed取模更简洁还少一个清零操作。4.3 筛法版本完整代码与逐段解析筛法完整代码在3.2小节已经给过这里补充一个更明确的版本并说明它和试除法版本的差异#include stdio.h #define MAX 110000 int isComposite[MAX]; int main() { int m, n; scanf(%d%d, m, n); for (int i 2; i * i MAX; i) { if (!isComposite[i]) { for (int j i * i; j MAX; j i) { isComposite[j] 1; } } } int count 0; for (int i 2; i MAX; i) { if (!isComposite[i]) { count; if (count m) { printf(%5d, i); if (count n) { if ((count - m 1) % 10 0) printf(\n); } else { break; } } } } if ((n - m 1) % 10 ! 0) printf(\n); return 0; }这段代码和3.2版本的差别在于换行判断方式。这里用(count - m 1) % 10来算“当前输出的是这一段的第几个”比之前的写法更直观。注意在break之前如果count已经是n且恰好是行末第10个换行已经在循环内处理了所以跳出循环后的补换行判断要小心。我个人更推荐3.2那个版本原因是“(count - m 1) % 10”这种写法在m接近n时容易把人绕晕而3.2里直接用printed变量思路更线性。写代码首要目标是让自己和别人都能看懂其次才是追求花哨。5. 常见问题与排查技巧实录5.1 输出格式的三类低级错误我见过太多人在这题上因为输出格式丢分甚至我自己第一次提交也栽在行末空格上。整理成速查表大家提交前逐个排查错误类型具体情况排查方法行末多空格手动在数字间加空格最后一个数字后面也带空格确保最后一个数字后面紧跟换行符而不是补一个空格宽度写错用%d而不是%5d输出导致与题目要求不符仔细读输出格式描述确认是否要求占5位宽度换行错误最后一行的换行缺失或满10个后多打一个换行用printed % 10判断循环结束后按% 10 ! 0决定是否补换行排查格式问题的方法很简单题目给的样例输入1 10先跑一遍把输出结果复制出来跟样例输出逐字符比对包括空格和换行。PAT的样例不能完全覆盖所有边界但格式问题靠样例就能暴露大半。5.2 运行超时不是算法错是写得太暴力如果提交后发现某个测试点超时优先怀疑isPrime里循环上界写成了i x。这种写法在本题目数据范围下也可能勉强通过但如果测试数据恰好卡得紧就会超时。另一个导致超时的原因是每输出一个素数后没有及时在count n时跳出循环程序会一直算到数组末尾或无限循环。试除法版本里我用while(1)配合判断break就是为了在找到第n个素数后立刻终止不再做无用的判断。还有一点是编译层面的如果你在PAT上选用了Ciostream的同步关闭问题也可能拖慢速度。刷题时我习惯用printf/scanf而不是cin/cout不是因为C比C好而是printf/scanf在数据量大时确实更稳。用cin/cout的话记得加一句ios::sync_with_stdio(false)。5.3 逻辑错误第几个素数和数值区间的混淆这个属于理解题面的问题但出现频率特别高。m5, n100时很多人以为要输出5到100之间所有的素数实际上要输出的是第5个素数11到第100个素数之间的所有素数。判断自己有没有理解错就用样例验证。题目如果给出m5, n20的样例第5个素数是11第20个素数是71输出从11到71的所有素数。如果你输出的是一串从5开始的素数那肯定是把“第几个”和“数值范围”搞混了。还有个隐藏考点M可能等于N。比如输入5 5应该只输出一个数第5个素数11。我的代码里通过count m count n的条件天然支持了这种情况不需要额外特殊处理。5.4 考场上的调试策略与练习建议说实话PAT乙级1013不算难题但它能很好地检验基础是否扎实。如果你正跟着翁恺老师的C语言课程学或者刚开始刷PAT题库我建议把这道题当作“输出格式训练”的第一课。具体练习步骤可以这样安排第一步不要看任何题解自己先写一版试除法代码提交一次看能得多少分。第二步对着测试样例检查格式修改到样例完全一致。第三步如果再超时或格式错误再回头看这篇文章里的排查表。第四步把筛法版本也写了并且保证两个版本都能AC再去找下一道题。我最初刷PAT的时候看到网上有人分享“PAT 1013用Python会不会超时”的帖子当时还没意识到不同语言在效率上的差距。后来自己试了一下同样的逻辑Python版在极端数据下确实不如C语言稳。如果你主学Python建议至少在PAT这类竞赛平台用C语言完成提交平时用Python练习思路就好。语言的选择要服务于“过题”这个目标。最后再分享一个我自己常用的调试技巧当你摸不准“第m个到第n个素数”到底应该输出多少个时直接在本地跑一组m1, n10的数据看看输出是不是恰好10个数字、最后一行是否以换行结尾。如果是说明逻辑基本正确如果数量不对优先检查计数器的自增位置是否正确。这个小习惯帮我省下了很多次无效提交的时间。