相关疑难解决方法(0)

只是为了澄清,这不是一个功课问题:)

我想找到我正在建造的数学应用程序的素数并且遇到了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)