资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

埃氏筛与线性筛：两种经典的素数筛选算法详解

创作时间:

作者:

@小白创作中心

埃氏筛与线性筛：两种经典的素数筛选算法详解

引用

CSDN

https://blog.csdn.net/m0_74824865/article/details/144706131

本文将详细介绍两种经典的素数筛选算法：埃氏筛和线性筛（欧拉筛）。通过对比分析，帮助读者理解它们的原理、实现方法以及应用场景。

一、埃氏筛

1.1 定义

埃氏筛（埃拉托斯特尼筛法）是一种古老且简单高效的用于筛选出一定范围内所有素数的算法。它是由古希腊数学家埃拉托斯特尼（Eratosthenes）提出的。

1.2 基本原理

素数是一个大于 1 且除了 1 和它自身外，不能被其他自然数整除的数。埃氏筛法基于一个简单的想法：一个素数的倍数一定不是素数；如，2 是素数，那么 2 的倍数（4、6、8、10 等）就不是素数；3 是素数，3 的倍数（6、9、12 等）也不是素数。但是这里会出现重复筛选的情况；比如12会被34筛除之后又会被26筛除；后面优化成线性筛就解决了这一点。

基于遍历2~n的i去依次乘primer数组的质数（也就是得到的合数的质因子)，完成对合数在st数组的标记。

1.3 算法代码实现

这里代码实现的确实比较简单；前提是基于我们对它的原理操作有一定理解之后而成的。

const int N = 1e8 + 10;
bitset<N> st;//模拟bool类型；0素数，1合数，暂时当数组用
int primer[N];//储存质数的数组
inline int set_primer(int n) {
    int k = 0;//标记有多少个素数
    for (int i = 2; i <= n; i++) {
        if (!st[i])primer[++k]=i;//如果是质数就放入primer数组储存
        for (int j = 1;primer[j]&& i * primer[j] <= n; j++) {
            st[i * primer[j]] = 1;//把st中真实为合数的值标记出来
        }
    }
    return k;
}

1.4 时间复杂度

埃氏筛法的时间复杂度是O(nlog logn)。这在处理大规模数据寻找素数时，相比简单的逐个判断每个数是否为素数（时间复杂度为n*n^0.5）的方法要快很多。

1.5 应用场景

它主要用于数学领域中素数的查找和相关数论问题的研究。在计算机科学领域，如密码学（例如 RSA 加密算法的基础部分涉及素数的生成和使用）等方面也有广泛的应用，因为素数在构建安全的加密体系等方面起着关键的作用。

二、线性筛（欧拉筛）

2.1 定义

线性筛，也叫欧拉筛，是一种用于筛选素数的算法。它在埃氏筛法的基础上进行了优化，能够以线性时间复杂度（即O(n)）来求出一定范围内的所有素数。

2.2 基本原理

线性筛的核心思想是每个合数只被它的最小质因数筛掉一次。这样就避免了埃氏筛法中一个合数可能被多个质因数重复筛选的情况，从而提高了效率。

这里当发现是primer数组中某个元素的倍数，就需要先把当前两者之积的合数标记完后退出后面的操作，为了保证：每个合数只被它的最小质因数筛掉一次。

2.3 算法代码实现

这里其实就是埃氏筛代码加了判断重复的优化：

const int N = 1e8 + 10;
bitset<N> st;//模拟bool类型；0素数，1合数，暂时当数组用
int primer[N];//储存质数的数组
inline int set_primer(int n) {
    int k = 0;//标记有多少个素数
    for (int i = 2; i <= n; i++) {
        if (!st[i])primer[++k]=i;//如果是质数就放入primer数组储存
        for (int j = 1;primer[j]&& i * primer[j] <= n; j++) {
            st[i * primer[j]] = 1;//把st中真实为合数的值标记出来
            if (i % primer[j] == 0) break;//线性筛的优化：保证每次最小质因子筛除
        }
    }
    return k;
}

2.4 时间复杂度

线性筛的时间复杂度是O(n)，这使得它在处理大规模数据筛选素数时效率非常高。例如，当需要在一个很大的范围内查找素数时，线性筛可以在较短的时间内完成任务。

2.5 应用场景

在数论相关的计算中，如计算一定范围内素数的个数、对数字进行质因数分解等操作。在密码学中，也常用于生成大素数等基础操作，为加密算法提供必要的数学支持。例如，在一些现代密码系统的密钥生成过程中，需要快速准确地获取大量素数，线性筛就可以发挥作用。

三、线性筛与埃氏筛的比较

①埃氏筛法简单易懂，但在筛选过程中会对合数进行多次标记，导致效率在一定程度上较低。例如，对于合数 12，在埃氏筛法中，当处理素数 2 时会标记 12（因为 12 是 2 的倍数），当处理素数 3 时也会标记 12（因为 12 是 3 的倍数）。

②线性筛通过巧妙的设计，保证每个合数只被标记一次，是由它的最小质因数来标记，从而实现了线性时间复杂度的筛选。

这里总结一句话就是：线性筛就是在埃氏筛基础上的优化，通过每次以最小质因子的筛除法去筛查，避免不必要的重复筛选，降低了时间复杂度。

四、设计时的细节问题

4.1 为什么要把埃氏筛优化成线性筛

也就是为什么我们要有这行代码？我们的目的是用最小质因数筛除来达到最终目的的。
下面我们画图推到一下公式理解一下：
下面通俗易懂一下我们来个示范：
假设我们i遍历到4，此时 42==8；符合规则；筛除，但是如果再次往下进行就是34；此时4不是12的最小质因数，就不能筛除了；因此要等到2*6来完成对12的筛除；故我们那时候就要break了。

4.2 为什么j不用根据下标判断是否越界

这里由于primer数组默认都是初始化0；当遇到0就是终止的时候；其次就是我们要求的是n范围内的为素数的数字放入primer数组；然后每次标记的就是iprimer[j]标记为合数（1）；当越界后就无需让它接着累乘primer[j+1]进行判断了，直接退出标记合数的for循环即可。
首先思考一下为什么不添加上j<=k呢？
*举个栗子：如此时合数就是4，那么此时primer数组肯定有2 3，当我们标记完24就会自己退出；当质数如5，此时是2,3,5当我们标记完25；后5mod5直接break了。*

五、应用实例题解

下面以一道洛谷的模版题测试一下：【模板】线性筛素数 - 洛谷

#include<bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10;
bitset<N> st;//模拟bool类型；0素数，1合数
int primer[N];
inline int set_primer(int n) {
    int k = 0;//标记有多少个素数
    for (int i = 2; i <= n; i++) {
        if (!st[i])primer[++k]=i;
        for (int j = 1;primer[j]&& i * primer[j] <= n; j++) {
            st[i * primer[j]] = 1;//把st中真实为合数的值标记出来
            if (i % primer[j] == 0) break;
        }
    }
    return k;
}
int main() {
    int x,y;
     scanf("%d %d",&x,&y);
     set_primer(x);
    while(y--){
        int t;
        scanf("%d",&t);
        printf("%d
",primer[t]);
    }
     return 0;
}

最后也是通过了。