线性筛素数
题目背景
本题已更新，从判断素数改为了查询第 �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
说明/提示
【数据范围】
对于 100%100% 的数据，�=108n=108，1≤�≤1061≤q≤106，保证查询的素数不大于 �n。
Data by NaCly_Fish.
#include
using namespace std;
const int N=1e8+10;
int n;
vector
vector
int main(){
std::ios::sync_with_stdio(0);//加速
cin.tie(nullptr);//优化
int n,q;cin>>n>>q;
a.resize(n+1);//重新定义数组长度
for(int i=2;i<=n;i++){//全假
if(a[i])continue;
p.push_back(i);//2 3 5 7
for(int j=1;i*j<=n;j++){//倍数
a[i*j]=true;//2 4 6 8...3 6 9 ...
}
}
while(q--){
int k;cin>>k;
cout< } return 0; } #include using namespace std; const int N=1e8+10; int n; vector vector int main(){ std::ios::sync_with_stdio(0);//加速 int n,q;cin>>n>>q; a.resize(n+1);//重新定义数组长度 for(int i=2;i<=n;i++){//假 if(a[i]==false) p.push_back(i); for(int j=0;j a[p[j]*i]=true; if(i%p[j]==0)break; } } while(q--){ int k;cin>>k; cout< } return 0; }