【狂热算法篇】解锁筛法密码：埃氏筛与线性筛（欧拉筛）的深度剖析

用户11458826

发布于 2025-01-23 18:59:06

5100

代码可运行

文章被收录于专栏：杀马特杀马特

运行总次数：0

代码可运行

本篇简介：

对于素数的筛选法进行优化而得出的埃氏筛，线性筛的引入，一些细节处理，如为什么这么设计，好处在哪等一系列问题的解释，最后设计出代码；以及例题示例。

在介绍前我们先观看一个视频看一下它是如何操作的：

筛选草图模拟

这里有点草率，但是还是可以看懂的，每次以遍历选中的倍数去标记成合数也就是1，每次遍历的都是素数，也就是为0，放入primer数组，直到达到我们设定的顶值n；后面会依次对下面的两种筛法做靠近调整（基于两个for嵌套方式不同以及优化的不同）。

所以下面的两种方法为什么可以做到筛选出指定范围内的质数呢？

剧透一下：我们不断去向st数组标记合数，而某个合数它一定是由一个质数与另一个数的乘积；那么此时当快遍历到这个合数的时候，它子质因子已经放入primer数组，它的另一个子数也已经和primer数组中的质数完成了筛选；故此时这个合数一定在st数组被标记了；这就造成了尽管st数组都是初始化0(都是素数，01不考虑)；还能保证每次放入primer数组的都是质数的原因了

一·埃氏筛：

埃氏筛草图模拟

这里我们只演示一部分，剩下的类似，我们演示了12被3*4筛除，后面它还会被2*6筛除（这就是埃氏筛的缺点）。

1.1定义：

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

1.2基本原理：

素数是一个大于 1 且除了 1 和它自身外，不能被其他自然数整除的数。埃氏筛法基于一个简单的想法：一个素数的倍数一定不是素数；如，2 是素数，那么 2 的倍数（4、6、8、10 等）就不是素数；3 是素数，3 的倍数（6、9、12 等）也不是素数。

但是这里会出现重复筛选的情况；比如12会被3*4筛除之后又会被2*6筛除；后面优化成线性筛就解决了这一点。

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

1.3算法代码实现：

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

set_primer函数：把指定n范围内的素数放入primer数组然后统计出个数。 st数组：标记0-n数是质数还是合数：初始化都0也就是都是素数后面标1标记出合数。 primer数组：统计出n范围的质数并放入。

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算法代码实现：

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

这里也许会说为什么if的这个判断条件要加在标记合数操作之后，因为当发现i和primer[j]成倍数时；此时的primer[j]*i得到的val的最小质因子也是priemr[j]故先标记玩再break。

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，此时 4*2==8；符合规则；筛除，但是如果再次往下进行就是3*4；此时4不是12的最小质因数，就不能筛除了；因此要等到2*6来完成对12的筛除；故我们那时候就要break了。

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

这里由于primer数组默认都是初始化0；当遇到0就是终止的时候；其次就是我们要求的是n范围内的为素数的数字放入primer数组；然后每次标记的就是i*primer[j]标记为合数（1）；当越界后就无需让它接着累乘primer[j+1]进行判断了，直接退出标记合数的for循环即可。

首先思考一下为什么不添加上j<=k呢？

举个栗子：如此时合数就是4，那么此时primer数组肯定有2 3，当我们标记完2*4就会自己退出；当质数如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\n",primer[t]);
	}
	 return 0;
}