我們如何優化埃拉托斯特尼篩法以在 Python 中高效產生質數？

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

埃拉托斯特尼篩法是尋找素數的經典演算法。然而，正確實現它以避免效能瓶頸至關重要。

原始實作

提供的 primes_sieve 函數維護候選素數列表並迭代刪除非素數通過遍歷列表並消除因子來求素。由於列表操作的成本很高，這種方法本質上效率很低。

基於字典的最佳化

改良的 primes_sieve1 函數使用字典來儲存素性標誌。雖然比基於列表的方法更快，但它仍然面臨挑戰。它以未定義的順序迭代字典，導致非素數因子的冗餘標記。此外，它將最終的字典轉換為列表，從而產生不必要的開銷。

正確且高效的實現

正確的埃拉托斯特尼篩法演算法利用布爾標誌列表來表明素性。 primes_sieve2 函數將所有數字的標誌初始化為 True，並將 0 和 1 的標誌設為 False。它迭代列表，透過將標誌設為 False 來標記非素數。

這種方法很有效，因為：

• 它使用列表而不是字典，避免了開銷鍵值運算。
• 僅將質因數標記為非質數，減少冗餘操作。
• 它透過從每個質數的平方而不是其雙倍開始來最佳化標記過程。

透過正確實施埃拉托斯特尼篩法，您可以顯著提高素數產生的性能，使其甚至適用於輸入限制較大，例如查找 200 萬以下的素數。

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