本文主要是介绍算法刷题【洛谷P3383】线性筛素数（线性筛素数，欧拉筛法模板），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

异想之旅：本人原创博客完全手敲，绝对非搬运，全网不可能有重复；本人无团队，仅为技术爱好者进行分享，所有内容不牵扯广告。本人所有文章仅在CSDN和个人博客（一定是异想之旅域名）发布，除此之外全部是盗文！

洛谷 P3383 线性筛素数

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

In 1：

100 5
1
2
3
4
5

Out 1：

2
3
5
7
11

数据范围

对于 100 % 100\% 100% 的数据， n = 1 0 8 n = 10^8 n=108， 1 ≤ q ≤ 1 0 6 1 \le q \le 10^6 1≤q≤106，保证查询的素数不大于 n n n。

保证查询的素数不大于 n n n ，又有 n ≤ 1 0 8 n ≤ 10^8 n≤108 ，即本题无需开 long long ，比赛时一定要注意这些细节（给自己和大家的提醒）！

题解

本题就是模板题，那么我们直接开始讲欧拉筛法。

原理很简单，我们从数字2开始记录下素数，并将每个数（不一定是质数合数）的一定范围内的所有整数倍标记为非素数。而重点就在于这个一定范围内如何处理，请大家先看代码，我们再讲解。

#include <bits/stdc++.h>
using namespace std;

int ss[100000001], cnt;  // ss: ss[i]表示第i个素数，cnt: ss的长度，即素数的个数
bool pd[100000001];  // pd: pd[i]表示i是否是素数

inline void read(int &x){  // 快读不说了
    x = 0;
    short fs = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')fs = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar();
    }
    x *= fs;
}

int main() {
    memset(pd, 1, sizeof(pd));  // 默认都是素数，一个一个筛出去
    pd[0] = pd[1] = 0;  // 0和1不是素数（其实不处理也无所谓不影响本题结果）
    int n, q, k;
    read(n);
    read(q);

    // 重点筛数的过程！！！
    for (int i = 2; i <= n; i++) {
        if (pd[i]) ss[++cnt] = i;  // 如果到了这一步仍没有筛掉i，说明i是素数，把它放入素数列表ss
        for (int j = 1; j <= cnt && ss[j] * i <= n; j++) {  // ①
            pd[ss[j] * i] = 0;  // (ss[j] * i)肯定是合数，所以把它标记好
            if(i % ss[j] == 0) break;  // ②
        }
    }

    while(q--){
        // q次询问，输出第k个素数
        read(k);
        printf("%d\n", ss[k]);
    }

    return 0;
}

①：在第32-34行是真正筛数的过程，会给合数打上标记。在循环条件 j <= cnt && ss[j] * i <= n 中，前者 j <= cnt 保证了 ss[j] 不选到不存在的素数；后者则是保证我们筛到的数小于最大可能要求的素数的值就好了，再往上筛在本题的要求下毫无意义。

②：按照我们目前的思路，我们按理要筛掉所有的满足 j <= cnt && ss[j] * i <= n 条件下的 ss[j] * i ，为什么还会有34行的判断？这就是欧拉筛的绝妙之处——每个数会且只会被筛一遍，大大提高了效率。

为了保证每个数只筛一次，本算法采用的思路是保证每个数字 z z z 都是被除了 1 1 1 和 z z z 本身之外的 最大因数 y y y × \times ×最小因数 x x x 筛掉。而每当 i % ss[j] == 0 时，对于 z = ( i × s s [ j + 1 ] ) z = (i \times ss[j+1]) z=(i×ss[j+1]) ，不应被 y = i y=i y=i， x = ( s s [ j + 1 ] ) x=(ss[j+1]) x=(ss[j+1]) 筛掉，而应被 y = { ( i / s s [ j ] ) ∗ s s [ j + 1 ] } y=\{(i / ss[j]) * ss[j+1]\} y={(i/ss[j])∗ss[j+1]}， x = s s [ j ] x=ss[j] x=ss[j] 筛掉才对。

证明完不重复，再来看正确性：观察程序发现，对于任意合数 z ′ z' z′ ，我们只要保证当 i = z ′ i=z' i=z′ 时 z ′ z' z′ 被标记即可。而 z ′ z' z′ 会被 y ′ × x ′ y' \times x' y′×x′ 筛出来， y ′ y' y′ 一定出现在 z ′ z' z′ 前，而 z ′ z' z′ 的最小因数 x ′ x' x′ 一定是一个质数（这个自己证吧，分类讨论奇数和偶数），且任意比 x ′ x' x′ 校的素数 x ′ ′ x'' x′′ 不是 y ′ y' y′ 的因数（否则 x ′ x' x′ 的值应为 x ′ ′ x'' x′′）。

https://www.luogu.com.cn/record/68521669，这是标准的欧拉筛也就是本文中给出的代码，五个点总用时3.12秒；https://www.luogu.com.cn/record/68521661，这是本文代码去掉第34行提交的结果，足足用了7.96秒，基本上是卡限时通过的。

参考资料：

P3383 【【模板】线性筛素数】【题解/笔记】 - Eon的小木屋 - 洛谷博客

这篇关于算法刷题【洛谷P3383】线性筛素数（线性筛素数，欧拉筛法模板）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！