埃拉托舍内斯的筛子-寻找素数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）而不是其双精度开始非素数标记的算法优化。）

Answer 2

def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)

Answer 3

要从数组（列表）的开头删除，需要向下移动该数组之后的所有项。这意味着以这种方式从前面开始删除列表中的每个元素是一个O（n^2）操作。

使用集合可以更有效地执行此操作：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

。。。或者，避免重新排列列表：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes