Python中的快速素数筛

Question

我一直在使用埃拉托色尼的筛经历素数生成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的主筛比较脚本,以列出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)(页面末尾的@andasasbriese)慢1.5倍.

Answer 2

您应该只使用该算法的“推迟”变体。将您的代码测试运行次数上限与 10 和 2000 万次进行比较，如下所示

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

与另一个，在相应的数字 664579 和 1270607 素数处运行，产生：

...
print( list( islice( (p for p in postponed_sieve() ), n-1, n+1))) 

显示您的代码运行速度“仅”提高了3.1 倍...3.3 倍。:)没有快 36 倍，正如你的计时由于某种原因显示的那样。

我认为没有人声称它是一个“理想的”素数生成器，只是它在概念上是一个干净清晰的生成器。所有这些素数生成函数实际上都是玩具，真正的东西是处理非常大的数字，无论如何使用完全不同的算法。

在较低的范围内，重要的是算法的时间复杂度，它应该在~ n^(1+a)，a < 0.1...0.2 经验增长阶数左右，这两者似乎确实如此。~ n^1.5拥有一个具有甚至是增长顺序的玩具生成器~ n^2玩起来毫无乐趣。