摘要：本文详解 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 | 筛法范围上限（106+510^6+5106+5） |
a[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是素数；从i=2i = 2i=2开始，标记iii的所有倍数为合数。
constintmaxn=1e6+5;boola[maxn];// a[i] == 0 表示 i 是素数// 筛选素数（埃拉托色尼筛法）for(inti=2;i*i<=maxn;i++){if(!a[i]){for(intj=2*i;j<=maxn;j+=i){a[j]=1;// 筛掉合数}}}
✅ Step 2. 提取前 10000 个素数
定义一个b数组用于存储前100001000010000个素数（即P1P_1P1到P10000P_{10000}P10000）：
遍历筛选数组
a；将素数依次填入
b数组；一旦素数数量达到100001000010000就停止。
intk=0;for(inti=2;i<=maxn;i++){// 提取前10000个素数if(!a[i]){b[++k]=i;if(k>10000)break;}}
✅ Step 3. 输出第PMP_MPM到第PNP_NPN个素数，并控制格式
设变量c记录当前输出的素数数量：
- 从b[m]b[m]b[m]输出到b[n]b[n]b[n]；
- 每输出一个数，
c++； - 每满 10 个数字输出换行；
- 最后一个数字后不输出空格或换行符，需特判。
intc=0;for(inti=m;i<=n;i++){cout<<b[i];c++;// 计数已输出数字个数if(i==n)continue;// 最后一个数字后不加空格或换行if(c%10==0)cout<<"\n";// 每 10 个换行elsecout<<" ";}✅ 完整代码
#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e6+5;boola[maxn];// a[i] == 0 表示 i 是素数intm,n,b[10005],k;intmain(){cin>>m>>n;// 筛选素数（埃拉托色尼筛法）for(inti=2;i*i<=maxn;i++){if(!a[i]){for(intj=2*i;j<=maxn;j+=i){a[j]=1;// 筛掉合数}}}// 提取前10000个素数for(inti=2;i<=maxn;i++){if(!a[i]){b[++k]=i;if(k>10000)break;}}// 输出格式控制intc=0;for(inti=m;i<=n;i++){cout<<b[i];c++;if(i==n)continue;// 最后一个数字后不加空格或换行if(c%10==0)cout<<"\n";elsecout<<" ";}return0;}🚧 常见错误提醒
| 错误类型 | 具体表现 |
|---|---|
| 输出格式错误 | 每 10 个数后未换行或最后一个数后输出空格 |
| 数组越界 | b[i]下标超出范围，找到第 10000 个素数就要 break 停止 |
| 素数预处理不足 | maxn太小找不到足够素数 |
✅ 总结归纳
- 本题本质是素数筛选 + 输出格式控制；
- 使用埃拉托色尼筛法，高效筛选前10410^4104个素数；
- 注意从第PmP_mPm个开始计数，不是从mmm本身；
- 时间复杂度：O(nloglogn)O(n \log\log n)O(nloglogn)
- 空间复杂度：O(n)O(n)O(n)，主要用于布尔筛选数组。
🧠 思维拓展
- 如果范围更大，可考虑线性筛法，复杂度O(n)O(n)O(n)；
- 你也可以尝试用
isPrime()函数暴力判断，但效率远低； - 输出格式控制是算法题常考点，建议写个通用模板练习。
