埃拉托斯特尼筛法算法： Python, C++ 例如：

由： 陈莎拉 陈莎拉
Hours 更新

埃拉托斯特尼筛法是最简单的素数筛法。它是一种素数算法，用于在给定的极限内搜索所有素数。素数筛法有多种。例如，埃拉托斯特尼筛法、阿特金筛法、桑德拉姆筛法等。

这个单词 ”筛” 指的是过滤物质的器皿。因此， Python 和其他语言中都提到了一种过滤素数的算法。

该算法以迭代方式筛选出素数。筛选过程从最小的素数开始。素数是大于 1 的自然数，只有两个因数，即 1 和数字本身。非素数的数字称为合数。

在埃拉托斯特尼法的筛选中，首先选择一个较小的素数，然后过滤掉它的所有倍数。这个过程在给定的范围内循环运行。

例如：

我们取 2 到 10 之间的数字。

埃拉托斯特尼筛法

应用埃拉托斯特尼筛法后，它将产生素数列表 2、3、5、7

埃拉托斯特尼筛法

算法 埃拉托斯特尼筛法

以下是埃拉托斯特尼筛选法的算法：

步骤1） 创建一个从 2 到给定范围 n 的数字列表。我们从 2 开始，因为它是最小且第一个素数。

步骤2） 选择列表中最小的数字 x（最初 x 等于 2），遍历列表，并通过标记所选数字的所有倍数来过滤相应的合数。

步骤3） 然后选择下一个素数或列表中最小的未标记数字并重复步骤 2。

步骤4） 重复上一步，直到 x 的值小于或等于 n 的平方根（x<=算法 埃拉托斯特尼筛法).

请注意： 数学推理很简单。数字范围 n 可以分解为：

n=a*b

同样，n =算法 埃拉托斯特尼筛法*算法 埃拉托斯特尼筛法

=（小于的因子 算法 埃拉托斯特尼筛法) * （因子大于 埃拉托斯特尼筛法)

因此至少有一个 主要原因 或者两者必须 <=算法 埃拉托斯特尼筛法。因此，遍历到 算法 埃拉托斯特尼筛法 足够了。

步骤5） 经过这四个步骤后，剩余未标记的数字将成为给定范围 n 上的所有素数。

计费示例：

让我们举一个例子看看它是如何工作的。

对于这个例子，我们将找到从 2 到 25 的素数列表。所以，n=25。

步骤1） 在第一步中，我们将取从 2 到 25 的数字列表，因为我们选择 n=25。

算法 埃拉托斯特尼筛法

步骤2） 然后我们选择列表中最小的数字 x。最初 x=2，因为它是最小的素数。然后我们遍历列表并标记 2 的倍数。

对于给定的 n 值，2 的倍数有：4、6、8、10、12、14、16、18、20、22、24。

埃拉托斯特尼筛法

请注意： 蓝色表示选中的数字，粉色表示被淘汰的倍数

步骤3） 然后我们选择下一个最小的未标记数字，即 3，并通过标记 3 的倍数重复上一步。

埃拉托斯特尼筛法

步骤4） 我们以同样的方式重复步骤 3，直到 x=埃拉托斯特尼筛法 或5。

埃拉托斯特尼筛法

步骤5） 其余未标记的数字将是从 2 到 25 的质数。

埃拉托斯特尼筛法

相关文章

伪代码

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

埃拉托斯特尼筛法 C/C++ 代码示例

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

输出：

2 3 5 7 11 13 17 19 23

Eratosthenes筛 Python 程序范例

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

输出：

2
3
5
7
11
13
17
19
23

分段筛

我们已经看到，埃拉托斯特尼筛法需要在整个数字范围内运行循环。因此，它需要 O(n) 内存空间来存储数字。当我们试图在很大的范围内寻找素数时，情况会变得复杂。为更大的 n 分配这么大的内存空间是不可行的。

可以通过引入一些新特征来优化算法。其思想是将数字范围划分为更小的部分，然后逐个计算这些部分中的素数。这是一种降低空间复杂度的有效方法。这种方法称为 分段筛。

可以通过以下方式实现优化：

  1. 使用简单的筛子找出 2 至 分段筛 并将它们存储在数组中。
  2. 将范围 [0…n-1] 划分为大小最多为 分段筛
  3. 对于每个段，遍历该段并标记在步骤 1 中找到的素数的倍数。此步骤需要 O(分段筛) 最大。

常规筛选法需要 O(n) 辅助内存空间，而分段筛选法需要 O(分段筛)，对于较大的 n 来说，这是一个很大的改进。该方法也有缺点，因为它没有提高时间复杂度。

复杂度分析

空间复杂度：

简单的埃拉托斯特尼筛法需要 O(n) 内存空间。分段筛法需要
O(复杂度分析）辅助空间。

时间复杂度：

常规埃拉托斯特尼筛法算法的时间复杂度为 O(n*log(log(n)))。下面将讨论这种复杂性背后的原因。

对于给定的数字 n，标记合数（即非素数）所需的时间是常数。因此，循环运行的次数等于-

n/2+n/3+n/5+n/7+……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

素数和的调和级数可以用 log(log(n)) 来推导。

（1/2 + 1/3 + 1/5 + 1/7 +…….∞）= log（log（n））

因此，时间复杂度将是-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * 对数（对数（n））

因此时间复杂度为 O(n * log(log(n)))

接下来，您将了解 帕斯卡的三角形

结语

  • 埃拉托斯特尼筛选法滤除给定上限内的素数。
  • 过滤素数从最小素数“2”开始。此过程以迭代方式进行。
  • 迭代直到 n 的平方根，其中 n 是给定的数字范围。
  • 经过这些迭代之后，剩下的数字就是素数。