一种快速素数筛在Python [英] A Fast Prime Number Sieve in Python

问题描述

我已经用埃拉托塞尼的筛经历素数生成中Python和人们吹捧作为相对快的选项，如在一小the回答优化素数代蟒蛇的一个问题，是不是直接和简单的实现，我这里有他们的对手效率。我执行下面给出

I have been going through prime number generation in python using the sieve of Eratosthenes and the solutions which people tout as a relatively fast option such as those in a few of the answers to a question on optimising prime number generation in python are not straightforward and the simple implementation which I have here rivals them in efficiency. My implementation is given below

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]

定时执行返回

Timing the execution returns

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

而在回答中描述上述链接的问题作为从Python食谱最快的方法，下面给出

While the method described in the answer to the above linked question as being the fastest from the python cookbook is given below

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

我的问题是，为什么人们吹嘘上述库克书这是比较复杂，因为理想的首要发生器？

My question is why do people tout the above from the cook book which is relatively complex as the ideal prime generator?

推荐答案

我改变你的code，以适应@unutbu的<一素筛比较脚本href="http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python">Fastest办法列出以下N的蟒蛇所有质数 如下：

I transformed your code to fit into the prime sieve comparison script of @unutbu at Fastest way to list all primes below N in python as follows:

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的脚本快速计算所有质数：LT;百万但比rwh_primes2慢实际1.5倍，rwh_primes1（1.2），rwh_primes（1.19）​​和primeSieveSeq（1.12）（@andreasbriese在页面末尾）。

On my MBPro i7 the script is fast calculating all primes < 1000000 but actually 1.5 times slower than rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) and primeSieveSeq (1.12) (@andreasbriese at the page end).

这篇关于一种快速素数筛在Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！