Eratosthenes筛选 - 寻找Primes Python

Question

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

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

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

(注意,这还包括在素数的square(i*i)处开始非素数标记而不是其double 的算法优化.)

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

Answer 4

快多了：

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))