题目背景
本题已更新，从判断素数改为了查询第 kk 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。
题目描述
如题，给定一个范围 nn，有 qq 个询问，每次输出第 kk 小的素数。
输入格式
第一行包含两个正整数 n,qn,q，分别表示查询的范围和查询的个数。
接下来 qq 行每行一个正整数 kk，表示查询第 kk 小的素数。
输出格式
输出 qq 行，每行一个正整数表示答案。
输入输出样例
输入 #1复制
100 5
1
2
3
4
5
输出 #1复制
2
3
5
7
11
说明/提示
【数据范围】
对于 100\%100% 的数据，n = 10^8n=108，1 \le q \le 10^61≤q≤106，保证查询的素数不大于 nn。
Data by NaCly_Fish.
这道题用埃式筛解题也不是不可以,不过应该会超时
所以这道题考察我们的应该是线性筛(即欧拉筛,下同）
而欧拉筛法的思想非常简单，就是我们要求每一个数都被且仅被其最小的质因数筛掉（这也是欧拉筛对于埃氏筛法的一个优化），这使得它的时间复杂度仅有O(n)
而有些同学可能要问了：埃式筛又是什么呢？
埃式筛的大体思想：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。（详见百度百科）
那么代码如下：
#include <bits/stdc++.h>
using namespace std;
bool a[100000001];
/*
a数组存储筛法表(0代表不是质数,1代表是质数),并且这里要注意,因为题目输入的数据比较大,
a数组开long long或int会爆空间!
*/
int p[700000],s = 0;//p数组储存质数表,s储存目前p数组中有几个质数(其实就是质数表目前要赋值的下标)
void pri(int n)//在1-n的范围内处理质数
{
for(int i = 2; i <= n; i++)
{
if(a[i] == 1)//如果a[i]是质数
{
s++;//则质数表长度+1
p[s] = i;//再把该数字填入表中
}
for(int j = 1; j <= s && i * p[j] <= n; j++)//j遍历质数表,并且i * p[j]还不能超过范围(也就是n)
{
a[i * p[j]] = 0;//因为i * p[j]一定是合数
if(i % p[j] == 0) break;
/*
如果这是第一次筛掉它,就直接break
(因为欧拉筛只被它的最小的质因子筛掉,这也是它对埃氏筛的剪枝操作)
*/
}
}
}
int main()
{
int n,q;//n是质数范围,q是有几组数据
cin>>n>>q;
memset(p,1,sizeof(a));//初始化成1(因为1代表是质数,后期在pri函数中再刷掉合数)
a[1] = 0;//因为1不是质数
pri(n);//欧拉筛
for(int i = 0; i < q; i++)//预处理完后再输入
{
int k;
cin>>k;
cout<<p[k]<<endl;//直接调用质数表中的第k个
}
return 0;
}
加油！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
