埃拉托色尼筛法 Python & C++
陈莎拉
什么是埃拉托色尼筛法？
埃拉托色尼筛法是最简单的素数筛法。它是一种用于找出给定范围内所有素数的素数算法。存在几种素数筛法，包括埃拉托色尼筛法、阿特金筛法和桑达拉姆筛法。
这个单词 ”筛“”指的是一种过滤物质的器具。同样，筛算法在 Python 以及其他语言指的是一种从整数列表中过滤掉质数的方法。
该算法采用迭代方法筛选素数。筛选过程从最小的素数开始。素数是大于 1 的自然数，它只有两个因数，即 1 和它本身。 Numbers 不是质数的数称为合数。
为什么要使用埃拉托色尼筛法？
埃拉托色尼筛法首先选择一个较小的素数，然后过滤掉它的所有倍数。该过程在一个给定的范围内循环运行，高效地生成小于等于 n 的所有素数，而无需对每个候选素数进行试除运算。
这使得素数筛法比逐个检查素数更快。它广泛应用于数论、密码学、哈希算法和算法竞赛等领域，这些领域都需要快速生成大量素数。
例如：
让我们选取 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 之间的质数。
伪Code
以下伪代码描述了埃拉托色尼筛法的基本结构，之后我们将它翻译成实际代码。
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++ Code 例如：
以下是完整的 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 程序范例
下列 Python 该程序使用布尔列表和 while 循环实现了相同的算法。
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 分配如此大的内存块是不切实际的。
可以通过引入一些新特征来优化算法。其思想是将数字范围划分为更小的部分，然后逐个计算这些部分中的素数。这是一种降低空间复杂度的有效方法。这种方法称为 分段筛。
可以通过以下方式实现优化：
- 使用简单的筛子找出 2 至
并将它们存储在数组中。 - 将范围 [0…n-1] 划分为大小最多为 .
- 对于每个线段，遍历该线段并标记步骤 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)))。
接下来，你将学习到…… 帕斯卡的三角形.
