我们如何优化埃拉托斯特尼筛算法以在 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中文网其他相关文章！