每日一题第四十五期洛谷线性筛质数

本文主要是介绍每日一题第四十五期洛谷线性筛质数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【模板】线性筛素数

题目背景

本题已更新，从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。

题目描述

如题，给定一个范围 $n$ ，有 $q$ 个询问，每次输出第 $k$ 小的素数。

输入格式

第一行包含两个正整数 $n, q$ ，分别表示查询的范围和查询的个数。

接下来 $q$ 行每行一个正整数 $k$ ，表示查询第 $k$ 小的素数。

输出格式

输出 $q$ 行，每行一个正整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据， $n = 10^8$ ， $\le q \le 10^6$ ，保证查询的素数不大于 $n$ 。

Data by NaCly_Fish.

AC代码：

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
//#define endl '\n'
using namespace std;typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e8 + 10;
//线性筛
int n;
int cnt;
int prime[M], q, st[M];
int main()
{scanf("%d %d", &n, &q);for(int i = 2; i <= n; i ++){if(!st[i]) prime[++ cnt] = i;//质数for(int j = 1; j <= cnt && prime[j] * i <= n; j ++){st[prime[j] * i] = 1;if(i % prime[j] == 0) break;}}while(q --){int k;scanf("%d", &k);printf("%d\n", prime[k]);}
}