【题目来源】
https://www.luogu.com.cn/problem/P3383
【题目描述】
给定一个范围 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。
【算法分析】
● 素数判断的经典代码，如下所示。但是，当 n 较大时（如 1e8），会非常耗时，最终导致 TLE。
bool isPrime(int n) { if(n<2) return false; for(int i=2; i<=sqrt(n); i++) { if(n%i==0) return false; } return true; }● 解决方法是先用高效的素数筛选算法（埃氏筛/欧拉筛）预处理出 1e8 以内的所有素数并存储，再通过数组直接查询第 k 小的素数（数组下标对应排名）。
其中，静态埃氏筛详见 →https://blog.csdn.net/hnjzsyjyj/article/details/157615246
#include<bits/stdc++.h> using namespace std; const int maxn=1e8+5; bool st[maxn]; //isPrime int p[maxn]; //prime int cnt; void e_sieve(int n) { //eratosthenes_sieve 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; e_sieve(n); while(q--) { cin>>k; cout<<p[k]<<"\n"; } return 0; } /* in: 100 5 1 2 3 4 5 out: 2 3 5 7 11 */但是，静态埃氏筛代码中定义了 maxn=1e8+5，对应的两个数组：
bool st[1e8+5]：占用约 1e8 字节 ≈ 100MB
int p[1e8+5]：占用约 4*1e8 字节 ≈ 400MB
总计约 500MB 内存，这还只是 1e8 的情况。
这在内存受限的情况下，可能会导致MLE（Memory Limit Exceeded，内存超限）。
解决方法是vector替代全局静态数组，核心是节省内存、提升灵活性、避免溢出。
因此，动态埃氏筛应运而生。
● 那么，在动态埃氏筛中，如何对一个含 n 个元素的 bool 型的 vector 初始化为 true？
方法一：创建 vector 的同时直接初始化为 true（最常用）
例如，vector<bool> st(n, true);
方法二：vector 已存在，需要将其重置为全 true
例如，st.assign(n, true);
【算法代码：动态埃氏筛】
#include<bits/stdc++.h> using namespace std; vector<bool> st; //isPrime vector<int> p; //prime void e_sieve(int n) { //eratosthenes_sieve st.assign(n+1,true); //0~n 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.push_back(i); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q,k; cin>>n>>q; e_sieve(n); while(q--) { cin>>k; cout<<p[k-1]<<"\n"; } return 0; } /* in: 100 5 1 2 3 4 5 out: 2 3 5 7 11 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/132352060
https://blog.csdn.net/hnjzsyjyj/article/details/149666210
https://blog.csdn.net/rstyduifudg/article/details/147163559
https://www.luogu.com.cn/problem/solution/P3383
