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

2026/7/4 9:12:03

摘要：本文详解 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`太小找不到足够素数