Python 中的埃拉托色尼篩法

Manav Narula 2022年5月18日
Python 中的埃拉托色尼篩法

埃拉托色尼篩法是一種非常常見的演算法,用於獲取給定數以下的素數。這個數字應該不到一千萬。

該演算法易於理解,並且經常在程式設計中實現。本教程將演示如何實現 Python 的埃拉托色尼篩演算法。

讓我們首先了解該演算法背後的邏輯。首先,我們寫下所有的數字 2 之間和提供的數字讓我們假設 50

然後我們取第一個素數 2,並標記所有大於其平方且能被 2 整除的數。然後我們對下一個素數 3 重複相同的操作。

執行相同的過程,直到素數 7 7 之後的下一個數的平方是 121 且大於 50。標記所有數字後,未標記的值是素數直到 50

下圖展示了最終結果。

質數 1 到 50 使用 Eratosthenes 篩

在 Python 中使用埃拉托色尼篩法

我們將首先建立所需範圍的列表。該列表將為給定索引標記 TrueFalse

最初,列表包含所有元素為 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 將值標記為 TrueFalse 以過濾掉素數。最終結果在一個列表中。

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

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

相關文章 - Python Algorithm