【题目来源】
洛谷：P3383 【模板】线性筛素数 - 洛谷
【题目描述】
如题，给定一个范围 \(n\)，有 \(q\) 个询问，每次输出第 \(k\) 小的素数。
【输入】
第一行包含两个正整数 \(n,q\)，分别表示查询的范围和查询的个数。
接下来 \(q\) 行每行一个正整数 \(k\)，表示查询第 \(k\) 小的素数。
【输出】
输出 \(q\) 行，每行一个正整数表示答案。
【输入样例】
100 5
1
2
3
4
5
【输出样例】
2
3
5
7
11
【算法标签】
《洛谷 P3383 线性筛素数》 #数学# #素数判断,质数,筛法# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1e8 + 5; // 数组最大容量
int vis[N]; // 标记数组，0表示质数，1表示合数
int prim[N]; // 存储质数的数组
int cnt; // 质数个数计数器
int n, q; // n: 范围上限，q: 查询次数// 线性筛法（欧拉筛）获取质数
void get_prim(int n)
{for (int i = 2; i <= n; i++){if (!vis[i]) // 如果i是质数{prim[++cnt] = i; // 将i存入质数数组}for (int j = 1; i * prim[j] <= n; j++) // 筛去i*prim[j]{vis[i * prim[j]] = 1; // 标记i*prim[j]为合数if (i % prim[j] == 0) // 关键优化：保证每个合数只被最小质因子筛去{break;}}}
}int main()
{// 关闭同步流，加速输入输出// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);get_prim(N); // 筛选出所有质数cin >> n >> q; // 读入范围上限和查询次数while (q--){int k;cin >> k; // 读入查询编号cout << prim[k] << endl; // 输出第k个质数}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 100000005; // 数组最大容量
int n, q, cnt; // n: 范围上限，q: 查询次数，cnt: 质数计数器
int primes[N]; // 存储质数的数组
bool st[N]; // 标记数组，false表示质数，true表示合数// 线性筛法（欧拉筛）获取质数
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) // 如果i是质数{primes[++cnt] = i; // 将i存入质数数组}for (int j = 1; primes[j] <= n / i; j++) // 筛去primes[j]*i{st[primes[j] * i] = true; // 标记primes[j]*i为合数if (i % primes[j] == 0) // 关键优化：保证每个合数只被最小质因子筛去{break;}}}
}int main()
{cin >> n >> q; // 读入范围上限和查询次数get_primes(N); // 筛选出所有质数while (q--){int k;cin >> k; // 读入查询编号cout << primes[k] << endl; // 输出第k个质数}return 0;
}
【运行结果】
100 5
1
2
2
3
3
5
4
7
5
11