1. 题目来源

2. 题意概述

输入两个整数：n q 其中：n 表示筛素数的范围;q  表示询问次数。接下来有 q 行,每行输入一个整数 k,要求输出：第 k 小的素数。本题数据量很大：n = 1e8  q 最多 1e6 所以不能每次询问都重新找素数,必须先预处理。

3. 解题思路

1. 先筛出所有素数,再直接查询

因为有很多次询问,应该先把 1 ~ n 之间的所有素数找出来,并按从小到大的顺序存入数组：

prime[1] = 2;prime[2] = 3;prime[3] = 5;prime[4] = 7;prime[5] = 11;

询问第 k 小的素数,答案就是：prime[k] 每次查询只需要 O(1) 时间。

2. 用 vis[x] 标记合数

bitset<N> vis; 含义是：

vis[x] = 0：x 还没有被标记,可能是素数vis[x] = 1：x 已经被标记为合数

在线性筛中,如果发现：if (!vis[i]) 就说明i 没有被任何更小的质因子筛掉,因此 i 是素数。于是把它加入素数表：prime[++cnt] = i;这里使用 ++cnt,是为了让素数数组从 1 开始存,prime[1] 表示第 1 小的素数,依此类推。

3. 线性筛的核心：每个合数只筛一次

线性筛的核心循环是：

for(int j = 1; j <= cnt; ++j){    if (prime[j] > n / i) break;    vis[i * prime[j]] = 1;    if (i % prime[j] == 0) break;}

用已经找到的素数 prime[j],去筛掉 i * prime[j]。

因为：i × prime[j] 一定是两个大于等于 2 的数相乘,所以它一定是合数。vis[i * prime[j]] = 1; 表示把这个合数标记掉。

4.  prime[j] > n / i

i * prime[j] > n 如果超过了 n,就不用继续筛了。但是直接写：if (i * prime[j] > n) break; 可能出现乘法溢出。更稳妥的写法是：if (prime[j] > n / i) break;

5.  i % prime[j] == 0 时要停止

最关键一句:if (i % prime[j] == 0) break; 它的作用是：

保证每个合数只被自己的最小质因子筛掉一次。

例如：

18 = 9 × 218 = 6 × 3

18 的最小质因子是 2。所以在线性筛中，18 应该在：i = 9, prime[j] = 2 时被筛掉。而不是在：i = 6, prime[j] = 3 时再次被筛掉。如果不加 break,答案不一定错,但会出现大量重复筛。

6. 使用 bitset

n = 1e8如果使用普通的 bool 数组：bool vis[100000000]; 通常大约需要:100MB 。bitset 是按二进制位存储的。bitset<N> vis;可以理解为：

用一个个 bit 来存 0 / 1 状态。

1 byte = 8 bit所以 bitset 理论上可以让 8 个标记状态只占 1 个字节。因此:bitset<100000000>大约只需要：100000000 bit ÷ 8 ≈ 12.5MB 比 bool 数组节省很多空间。

4. 完整 AC 代码

#include<bits/stdc++.h>using namespace std;const int N = 100000010;// vis[x] = 0：表示 x 目前没有被标记，可能是素数// vis[x] = 1：表示 x 已经被标记为合数bitset<N> vis;// 1e8 以内的素数个数约是 5761455// prime[k] 表示第 k 小的素数,例如：prime[1] = 2int prime[6000000];int cnt = 0;// cnt 表示当前已经找到多少个素数int n, q;// 线性筛函数：筛出 1 ~ n 之间的所有素数voidlinearSieve(){    // 从 2 开始枚举    // 因为 0 和 1 都不是素数    for(int i = 2; i <= n; ++i){        // 如果 i 没有被标记为合数,说明 i 是素数        if (!vis[i]) prime[++cnt] = i;        // 用已经找到的素数 prime[j] 去筛掉 i * prime[j]        for(int j = 1; j <= cnt; ++j){            // 如果 i * prime[j] > n,就不能继续筛了            // 不直接写：if (i * prime[j] > n) break;            // 避免 i * prime[j] 乘法溢出            if (prime[j] > n / i) break;            // i * prime[j] 一定是合数            vis[i * prime[j]] = 1;            // 线性筛最关键的一句            // 如果 prime[j] 能整除 i，            // 说明 prime[j] 是 i 的最小质因子            // 那么 i * prime[j] 已经被自己的最小质因子筛掉了            // 后面更大的质数再乘 i,会造成重复筛,所以这里必须停止            if (i % prime[j] == 0) break;        }    }}intmain(){    ios::sync_with_stdio(0);    cin.tie(0);    cin >> n >> q;    linearSieve();// 先把 1 ~ n 范围内的所有素数筛出来    // 回答 q 次询问    while(q--){        int k;   cin >> k;        // prime[k] 就是第 k 小的素数        cout << prime[k] << '\n';    }    return 0;}

点击↓ 阅读原文 可提交代码