Eratosties筛-寻找Python的Primes

Question

Eratosties筛-寻找Python的Primes我只想澄清一点，这不是家庭作业的问题：)我想为我正在构建的数学应用程序找到素数&偶然发现的。埃拉托斯提尼筛接近。我已经用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 primesprint 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 primesprint 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