Sieve of Eratosthenes - Finding Primes Python

Question

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

我已经用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维护素数标志的字典，这是朝着正确方向迈出的一步，但是它以未定义的顺序遍历该字典，并且多余地剔除了素因数（而不是像算法中那样仅素数因数） ）。你可以通过对键进行排序并跳过非撇号（这已经使其速度提高了一个数量级）来解决此问题，但是直接使用列表的效率仍然更高。

正确的算法（使用列表而不是字典）看起来像：

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）而不是其双数开始的非素数标记的算法优化。）