PAT 乙级题目讲解：1013《数素数》

摘要本文详解 PAT 乙级 1013 题《数素数》要求输出第PMP_MPM​到第PNP_NPN​个素数。通过埃拉托色尼筛法高效预处理前 10000 个素数并严格控制输出格式——每行最多 10 个末尾无多余空格。文章涵盖题目分析、解题思路、完整代码、常见错误提醒以及总结拓展。✅ PAT 乙级题目讲解1013《数素数》 题目简介本题要求输出第PMP_MPM​到第PNP_NPN​个素数其中PiP_iPi​表示第iii个素数。输出格式为每行最多输出 10 个素数素数之间用空格隔开末尾不得多输出空格或换行。 样例分析输入5 27前 27 个素数依次为2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103我们需要输出从第 5 个素数即 11到第 27 个素数即 103之间的所有素数共 23 个。输出格式要求每行最多输出 10 个素数素数之间用空格隔开最后一行末尾不能有多余空格。输出11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 解题思路本题是典型的素数筛选 输出格式控制问题。 变量说明变量名含义maxn筛法范围上限106510^651065a[i]素数筛标记0 表示是素数1 表示是合数b[i]存储前若干个素数第 i 个素数为b[i]m, n题目给定的 M, N输出第 m 到第 n 个素数k当前已经找到的素数个数用于填充 b 数组c当前已经输出了多少个素数用于换行控制本题的解决流程可以分为以下几个步骤✅ Step 1. 筛选素数埃拉托色尼筛法我们使用埃拉托色尼筛法预处理一定范围内的素数设置最大范围maxn 1e6 5保证可以筛出前 10000 个素数a[i] 0表示iii是素数从i2i 2i2开始标记iii的所有倍数为合数。constintmaxn1e65;boola[maxn];// a[i] 0 表示 i 是素数// 筛选素数埃拉托色尼筛法for(inti2;i*imaxn;i){if(!a[i]){for(intj2*i;jmaxn;ji){a[j]1;// 筛掉合数}}}✅ Step 2. 提取前 10000 个素数定义一个b数组用于存储前100001000010000个素数即P1P_1P1​到P10000P_{10000}P10000​遍历筛选数组a将素数依次填入b数组一旦素数数量达到100001000010000就停止。intk0;for(inti2;imaxn;i){// 提取前10000个素数if(!a[i]){b[k]i;if(k10000)break;}}✅ Step 3. 输出第PMP_MPM​到第PNP_NPN​个素数并控制格式设变量c记录当前输出的素数数量从b[m]b[m]b[m]输出到b[n]b[n]b[n]每输出一个数c每满 10 个数字输出换行最后一个数字后不输出空格或换行符需特判。intc0;for(intim;in;i){coutb[i];c;// 计数已输出数字个数if(in)continue;// 最后一个数字后不加空格或换行if(c%100)cout\n;// 每 10 个换行elsecout ;}✅ 完整代码#includebits/stdc.husingnamespacestd;constintmaxn1e65;boola[maxn];// a[i] 0 表示 i 是素数intm,n,b[10005],k;intmain(){cinmn;// 筛选素数埃拉托色尼筛法for(inti2;i*imaxn;i){if(!a[i]){for(intj2*i;jmaxn;ji){a[j]1;// 筛掉合数}}}// 提取前10000个素数for(inti2;imaxn;i){if(!a[i]){b[k]i;if(k10000)break;}}// 输出格式控制intc0;for(intim;in;i){coutb[i];c;if(in)continue;// 最后一个数字后不加空格或换行if(c%100)cout\n;elsecout ;}return0;} 常见错误提醒错误类型具体表现输出格式错误每 10 个数后未换行或最后一个数后输出空格数组越界b[i]下标超出范围找到第 10000 个素数就要 break 停止素数预处理不足maxn太小找不到足够素数✅ 总结归纳本题本质是素数筛选 输出格式控制使用埃拉托色尼筛法高效筛选前10410^4104个素数注意从第PmP_mPm​个开始计数不是从mmm本身时间复杂度O(nlog⁡log⁡n)O(n \log\log n)O(nloglogn)空间复杂度O(n)O(n)O(n)主要用于布尔筛选数组。 思维拓展如果范围更大可考虑线性筛法复杂度O(n)O(n)O(n)你也可以尝试用isPrime()函数暴力判断但效率远低输出格式控制是算法题常考点建议写个通用模板练习。