埃拉托舍内斯的筛子-寻找素数Python

Question

只是澄清一下，这不是一个家庭作业问题：）

我想为我正在构建的数学应用程序找到素数&；comedSieve 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维护了素性标志的字典，这是朝着正确方向迈出的一步，但它以未定义的顺序在字典上迭代，并冗余地删除因子中的因子（而不只是素数的因子，如在算法中）。您可以通过对键进行排序并跳过非素数（这已经使它的速度提高了一个数量级）来解决这个问题，但是直接使用列表仍然有效得多。

正确的算法（使用列表而不是字典）类似于：

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