我们如何优化埃拉托色尼筛以在 Python 中更快地生成素数？

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

埃拉托斯特尼筛法是一种历史悠久的算法，用于识别指定限制内​​的素数。虽然实现起来很简单，但对于较大的限制，它可能会非常慢。

实现缓慢

以下筛子的 Python 实现面临着效率方面的挑战：

def primes_sieve(limit):
    primes = range(2, limit+1)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)

瓶颈在于随着数字的删除而不断调整素数列表的大小。从 Python 列表中删除项目涉及移动后续元素，使其成为计算成本高昂的操作。

使用字典更快地实现

为了解决这个问题，基于字典的实现可以使用：

def primes_sieve1(limit):
    primes = dict()
    for i in range(2, limit+1): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False

这维护了素数标志的字典，减少了调整大小操作的需要。然而，以未定义的顺序迭代字典键并重复标记非素数的非素因数会限制效率。

使用 List 的更正算法

正确的实现更紧密地遵循埃拉托斯特尼筛法：

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

这维护了一个列表素数标志，将除 0 和 1 之外的所有数字初始化为素数。它将素数的倍数标记为非素数，从素数的平方开始优化流程。

通过解决实现中的效率问题，这个修正后的算法显着提高了素数生成的速度，即使在很大的限制下也是如此。

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