题目背景
本题已更新，从判断素数改为了查询第 k 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。
题目描述
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
输入格式
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。
输出格式
输出 q 行，每行一个正整数表示答案。
输入输出样例
输入 #1
100 5
1
2
3
4
5
输出 #1
2
3
5
7
11
说明/提示
【数据范围】
对于 ，保证查询的素数不大于 n。
Data by NaCly_Fish.
思路
这道线性筛素数用的欧拉筛法，我之前的博客写过暴力求解和普通筛法：
204. 计数质数（C++）
源码
#include<bits/stdc++.h>
using namespace std;
int prime[6000010];
bool isprime[100000010];
int n, q;
void ola()
{
memset(isprime, 1, sizeof(isprime));
int num = 0;
isprime[1] = 0;
for (int i = 2; i <= n; i++)
{
if (isprime[i])
prime[++num] = i;
for (int j = 1; i * prime[j] <= n && j <= num; j++)
{
isprime[i * prime[j]] = 0;
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>q;
ola();
while (q--)
{
int k;
cin >> k;
cout << prime[k] << endl;
}
return 0;
}
