线性筛素数
题目背景
本题已更新，从判断素数改为了查询第 �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<bits/stdc++.h>//埃氏筛 把后面筛掉
using namespace std;
const int N=1e8+10;
int n;
vector<int>p;
vector<bool>a;
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<<p[k-1]<<endl;
}
return 0;
}
#include<bits/stdc++.h>//欧拉筛选
using namespace std;
const int N=1e8+10;
int n;
vector<int>p;
vector<bool>a;
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<p.size()&&1ll*p[j]*i<=n;j++){
a[p[j]*i]=true;
if(i%p[j]==0)break;
}
}
while(q--){
int k;cin>>k;
cout<<p[k-1]<<endl;
}
return 0;
}