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 以過濾掉素數。最終結果在一個列表中。
作者： 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