3068: 【普及-】【P3383】线性筛素数
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：7
解决：3
题目描述
如题，给定一个范围 ，有 个询问，每次输出第 小的素数。对于 的数据，，，保证查询的素数不大于 。
输入
第一行包含两个正整数 ，分别表示查询的范围和查询的个数。
接下来 行每行一个正整数 ，表示查询第 小的素数。
输出
输出 行，每行一个正整数表示答案。
样例输入 复制
100 5
1
2
3
4
5样例输出 复制
2
3
5
7
11提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000010
bool is_prime[MAXN];
int prime[MAXN];
//埃筛
int Er_Sieve(int n){
int tot=0;
memset(is_prime,1,sizeof(is_prime));
is_prime[1] = is_prime[0] = 0;
for(int i = 2;i <= n;i++){
if(!is_prime[i]) continue;
prime[++tot] = i; //prime[]存储了[1,n]的所有质数
for(int j = i*2; j <= n; j+=i)
is_prime[j]=0; //j为合数
}
return tot;
}
//线性筛（欧拉筛）
int Eu_Sieve(int n){
int tot=0;
memset(is_prime,1,sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= n; i++){
if(is_prime[i])
prime[++tot] = i; //prime[]存储了[1,n]的所有质数
for(int j = 1; j <= tot && prime[j]*i <= n; j++){ //关键一
is_prime[prime[j]*i] = 0;
if(i%prime[j] == 0) break;// 关键二
}
}
return tot;
}
int n,q,k;
int main(){
int n;
scanf("%d %d", &n, &q);
Eu_Sieve(n);
while(q--) {
scanf("%d", &k);
printf("%d\n", prime[k]);
}
return 0;
}