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

🔍 解题思路

本题是典型的素数筛选 + 输出格式控制问题。

📎 变量说明

本题的解决流程可以分为以下几个步骤：

✅ 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;}

🚧 常见错误提醒

✅ 总结归纳

• 本题本质是素数筛选 + 输出格式控制；
• 使用埃拉托色尼筛法，高效筛选前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()函数暴力判断，但效率远低；
• 输出格式控制是算法题常考点，建议写个通用模板练习。