题目背景
本题已更新，从判断素数改为了查询第 k 小的素数。
提示：本题输入输出、运算数据量较大。
- 对于 C++ 语言，如果你使用
cin来输入输出，建议使用std::ios::sync_with_stdio(0)来加速，同时使用'\n'换行输出。 - 对于 Java 语言，使用线性筛并且优化输入输出，也可以在规定时限内通过本题，但是时限可能较紧张。
- 对于 Python 语言，语言性能差异较大，需要使用到
numpy库的数组以替代列表，且使用埃氏筛法，依然可以在合适的时间和内存消耗下通过本题。
题目描述
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
输入格式
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。
输出格式
输出 q 行，每行一个正整数表示答案。
输入输出样例
输入 #1复制
100 5 1 2 3 4 5
输出 #1复制
2 3 5 7 11
说明/提示
【数据范围】
对于 100% 的数据，n=108，1≤q≤106，保证查询的素数不大于 n。
Data by NaCly_Fish.
代码实现：
#include <iostream>
#include <vector>
using namespace std;
const int max11 = 1e6 + 1;
// 标记数组，用于标记每个数是否为质数
bool isPrime[max11];
// 存储质数的数组
vector<int> primes;
// 使用埃拉托斯特尼筛法筛选质数
void sieve(int n) {
// 初始化所有数为质数
for (int i = 2; i <= n; ++i)
{
isPrime[i] = true;
}
for (int i = 2; i * i <= n; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 将质数存入 primes 数组
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
}
}
int main() {
int n, k, m;
cin >> n >> k;
sieve(n);
while (k--) {
cin >> m;
// 输出第 m 个质数
cout << primes[m - 1] << endl;
}
return 0;
}
