我們如何優化埃拉托斯特尼篩演算法以在 Python 中更快地產生質數？

埃拉托斯特尼篩法改良：最佳化Python 素數產生

埃拉托斯特尼篩法是一種有效的演算法，用於尋找達到預定義限制的質數。然而，對於較大的限制，簡單的 Python 實作可能會變得非常慢。

辨識瓶頸

在提供的範例中，分析顯示從清單（素數）。此操作的計算成本很高，特別是對於長列表。

用字典替換列表

解決此問題的初步嘗試涉及用字典（素數）替換列表。這允許更快的元素移除。然而，演算法仍然存在：

• 以未定義的順序迭代字典
• 非素數因子的冗餘標記

實作正確的演算法

全面最佳化演算法，需要進行修正：

1. 使用列表而不是字典作為素數標誌
2. 跳過非素數因子
3. 在素數處開始因子標記正方形，而不是它的雙倍

最佳化演算法

優化演算法(primes_sieve2) 採用布林值列表作為質數標誌。它將所有大於 1 的數字初始化為 True。然後，它迭代列表，標記非素數：

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

透過優化這些關鍵方面，演算法顯著提高了其性能，發現在幾秒鐘內素數可達 200 萬。

以上是我們如何優化埃拉托斯特尼篩演算法以在 Python 中更快地產生質數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！