我們如何在 Python 中優化埃拉托斯特尼篩演算法以加快素數生成速度？

埃拉托斯特尼篩法- 在Python 中查找素數

問題：

嘗試實作時Python中的埃拉托色尼篩法演算法，使用者經常會遇到執行速度慢的情況，特別是在搜尋 100 萬以上的質數時。

解決方案：

給定的實作提出了幾個需要改進的領域：

1.未最佳化的演算法：

• 初始實作primes_sieve維護素數列表，導致元素刪除效率低。
• primes_sieve1 使用字典作為素數標誌，但缺乏適當的迭代和冗餘因素標記。

2.清單操作效率低：

• 從 Python 清單中刪除元素是一項昂貴的操作，因為需要移動後續元素。

最佳化實作:

要解決這些問題，請考慮以下最佳化實作：

def primes_sieve2(limit):
    a = [True] * limit
    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

主要改進：

• 直接使用列表作為素數標誌，避免昂貴的列表調整大小。
• 延遲產生按需素數，無需儲存完整的素數清單。
• 從素數平方開始，有效標記非素數因子。

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