python - Python 中的快速素数筛选

Question

我一直在使用 Eratosthenes 筛法和人们吹捧为相对快速的解决方案(例如 the answers to a question on optimising prime number generation in python 中的一些解决方案)在 Python 中生成素数。并不简单，我这里的简单实现在效率上可以与它们相媲美。下面给出我的实现

def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return sieve


print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0]

计时执行返回

python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)"
10 loops, best of 3: 19.5 msec per loop

虽然上面链接问题的答案中描述的方法是 python 食谱中最快的方法，但下面给出了

import itertools
def erat2( ):
    D = {  }
    yield 2
    for q in itertools.islice(itertools.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = p + q
            while x in D or not (x&1):
                x += p
            D[x] = p

def get_primes_erat(n):
  return list(itertools.takewhile(lambda p: p<n, erat2()))

运行时给出

python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)"
10 loops, best of 3: 697 msec per loop

我的问题是，为什么人们会把相对复杂的食谱中的上述内容吹捧为理想的素数生成器？

Answer 1

我转换了你的代码以适应@unutbu 在Fastest way to list all primes below N 的素筛比较脚本。 如下:

def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

在我的 MBPro i7 上，脚本可以快速计算所有小于 1000000 的素数，但实际上比 rwh_primes2、rwh_primes1 (1.2)、rwh_primes (1.19) 和 primeSieveSeq (1.12) 慢 1.5 倍(@andreasbriese 在页尾)。