我們如何優化埃拉托色尼篩以在 Python 中更快地生成素數？

在Python 中使用埃拉托斯特尼篩法優化素數產生

埃拉托斯特尼篩法是一種歷史悠久的演算法，用於識別指定限制內的質數。雖然實現起來很簡單，但對於較大的限制，它可能會非常慢。

實現緩慢

以下篩子的Python 實現面臨著效率方面的挑戰：

def primes_sieve(limit):
    primes = range(2, limit+1)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)

瓶頸在於隨著數字的刪除而中斷調整素數列表的大小。從 Python 清單中刪除項目涉及移動後續元素，使其成為計算成本高的操作。

使用字典更快實現

為了解決這個問題，基於字典的實作可以使用：

def primes_sieve1(limit):
    primes = dict()
    for i in range(2, limit+1): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False

這維護了素數標誌的字典，減少了調整大小操作的需要。然而，以未定義的順序迭代字典鍵並重複標記非素數的非素因數會限制效率。

使用List 的更正演算法

正確的實現更緊密地遵循埃拉托斯特尼篩法：

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

這維護了一個列表質數標誌，將除0 和1 之外的所有數字初始化為質數。它將質數的倍數標記為非素數，從素數的平方開始最佳化流程。

透過解決實現中的效率問題，這個修正的演算法顯著提高了素數產生的速度，即使在很大的限制下也是如此。

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