Python 中的埃拉托色尼筛法
Manav Narula
2022年5月18日
埃拉托色尼筛法是一种非常常见的算法，用于获取给定数以下的素数。这个数字应该不到一千万。
该算法易于理解，并且经常在编程中实现。本教程将演示如何实现 Python 的埃拉托色尼筛算法。
让我们首先了解该算法背后的逻辑。首先，我们写下所有的数字 2 之间和提供的数字让我们假设 50。
然后我们取第一个素数 2，并标记所有大于其平方且能被 2 整除的数。然后我们对下一个素数 3 重复相同的操作。
执行相同的过程，直到素数 7 7 之后的下一个数的平方是 121 且大于 50。标记所有数字后，未标记的值是素数直到 50。
下图展示了最终结果。
在 Python 中使用埃拉托色尼筛法
我们将首先创建所需范围的列表。该列表将为给定索引标记 True 或 False。
最初，列表包含所有元素为 True。我们将使用嵌套循环进行更改并将非主要位置标记为假。
在此之后，我们将值仍然为 True 的位置存储在一个新列表中。此列表包含素数。
def sieve_of_eratosthenes(val):
max = val+1
lst = [True] * max
for i in range(2, int(val**0.5 + 1)):
if lst[i]:
for j in range(i*i, max, i):
lst[j] = False
final = []
for i in range(2, max):
if lst[i]:
final.append(i)
return final
print(sieve_of_eratosthenes(100))
输出：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
可以对上述代码进行微小的更改以提高时间复杂度。例如，我们可以使用集合或字典来过滤非质数。
最终结果以列表形式返回，但使用字典或集合同时将素数和非素数数字标记为真或假。
def sieveoferatosthenes_dict(n):
max = n+1
d = dict()
for i in range(2, max): d[i] = True
for i in d:
factors = range(i,max, i)
for f in factors[1:]:
d[f] = False
lst = [i for i in d if d[i]==True]
return lst
print(sieveoferatosthenes_dict(100))
输出：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
在上面的示例中，我们使用字典 d 将值标记为 True 或 False 以过滤掉素数。最终结果在一个列表中。
Author: Manav Narula
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn