【题目来源】
【题目描述】
给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
【输入格式】
第一行包含两个正整数 n，q，分别表示查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。
【输出格式】
输出 q 行，每行一个正整数表示答案。
【输入样例】
100 5
1
2
3
4
5
【输出样例】
2
3
5
7
11
【数据范围】
对于 100% 的数据，n=10^8，1≤q≤10^6，保证查询的素数不大于 n。
【算法分析】
● 先用高效的素数筛选算法（埃氏筛优化版 / 线性筛）预处理出 10^8 以内的所有素数并存储，再通过数组直接查询第 k 小的素数（数组下标对应排名）。
● 执行示例（以 n=10 为例）如下所示
（1）初始化 st[0...10] = [true, true, true, true, true, true, true, true, true, true, true]。
（2）手动标记 st[0]=st[1]=false，此时 st = [f, f, t, t, t, t, t, t, t, t, t]。
（3）外层循环 i 从 2 开始（i*i<=10，即 i<=3）：
○ i=2：st[2]=true（素数），内层循环从 j=4 开始，标记 4、6、8、10 为 false，此时 st[4/6/8/10]=f。
○ i=3：st[3]=true（素数），内层循环从 j=9 开始，标记 9 为 false，此时 st[9]=f。
○ i=4：4*4=16>10，循环终止。
（4）最终 st 数组：[f, f, t, t, f, t, f, t, f, f, f]。
（5）未被标记为 false 的数（2、3、5、7）就是 10 以内的素数，符合预期。
【算法代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e8+5;
bool st[maxn]; //isPrime
int p[maxn]; //prime
int cnt;void seive(int n) {memset(st,true,sizeof st);st[0]=st[1]=false;for(int i=2; i*i<=n; i++) {if(!st[i]) continue;for(int j=i*i; j<=n; j+=i) st[j]=false;}for(int i=2; i<=n; i++) {if(st[i]) p[++cnt]=i;}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,q,k;cin>>n>>q;seive(n);while(q--) {cin>>k;cout<<p[k]<<"\n";}return 0;
}/*
in:
100 5
1
2
3
4
5out:
2
3
5
7
11
*/
【参考文献】