我们如何优化埃拉托斯特尼筛法以在 Python 中高效生成素数？

埃拉托斯特尼筛法：在 Python 中优化素数生成

埃拉托斯特尼筛法是寻找素数的经典算法。然而，正确实现它以避免性能瓶颈至关重要。

原始实现

提供的 primes_sieve 函数维护候选素数列表并迭代删除非素数通过遍历列表并消除因子来求素。由于列表操作的成本很高，这种方法本质上效率很低。

基于字典的优化

改进的 primes_sieve1 函数使用字典来存储素性标志。虽然比基于列表的方法更快，但它仍然面临挑战。它以未定义的顺序迭代字典，导致非素数因子的冗余标记。此外，它将最终的字典转换为列表，从而产生不必要的开销。

正确且高效的实现

正确的埃拉托斯特尼筛法算法利用布尔标志列表来表明素性。 primes_sieve2 函数将所有数字的标志初始化为 True，并将 0 和 1 的标志设置为 False。它迭代列表，通过将标志设置为 False 来标记非素数。

这种方法很有效，因为：

• 它使用列表而不是字典，避免了开销键值运算。
• 仅将质因数标记为非质数，减少冗余操作。
• 它通过从每个素数的平方而不是其双倍开始来优化标记过程。

通过正确实施埃拉托斯特尼筛法，您可以显着提高素数生成的性能，使其甚至适用于输入限制较大，例如查找 200 万以下的素数。

以上是我们如何优化埃拉托斯特尼筛法以在 Python 中高效生成素数？的详细内容。更多信息请关注PHP中文网其他相关文章！