小编典典

Sieve of Eratosthenes - Finding Primes Python

python

我想为正在构建的数学应用程序找到质数,并遇到了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)

阅读 55

收藏
2020-02-14

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

2020-02-14

回答这个问题

Nothing to preview