python - 埃拉托色尼筛 - 寻找素数 Python

Question

澄清一下，这不是作业问题:)

我想为我正在构建的数学应用程序找到素数并遇到了 Sieve of Eratosthenes方法。

我已经用 Python 编写了它的实现。但这非常慢。例如，如果我想找到所有小于 200 万的素数。它需要> 20分钟。 (我在这一点上停止了它)。如何加快速度？

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

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

print primes_sieve(2000)

更新:我最终对这段代码进行了分析，发现从列表中删除一个元素花了很多时间。考虑到它必须遍历整个列表(最坏情况)才能找到元素，然后将其删除，然后重新调整列表(也许还有一些副本？)，这是可以理解的。无论如何，我把字典列表扔掉了。我的新实现 -

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

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

print primes_sieve1(2000000)

Answer 1

你没有完全实现正确的算法:

在您的第一个示例中，primes_sieve 不维护要触发/取消设置的素数标志列表(如算法中所示)，而是不断调整整数列表的大小，这非常昂贵:从列表中删除一个项目需要将所有后续项目向下移动一个。

在第二个示例中，primes_sieve1 维护一个 dictionary 素数标志，这是朝着正确方向迈出的一步，但它以未定义的顺序迭代字典，并且多余地剔除因数的因数(而不是像算法中那样只剔除素数的因数)。您可以通过对键进行排序并跳过非素数来解决此问题(这已经使其速度提高了一个数量级)，但直接使用列表仍然效率更高。

正确的算法(使用列表而不是字典)看起来像:

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

(请注意，这还包括在素数的平方(i*i)而不是其双倍开始非素数标记的算法优化。)