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