我们如何在 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中文网其他相关文章！