列出N以下所有素数的最快方法

Question

列出N以下所有素数的最快方法

这是我能提出的最佳算法。

def get_primes(n):

    numbers = set(range(n, 1, -1))

    primes = []

    while numbers:

        p = numbers.pop()

        primes.append(p)

        numbers.difference_update(set(range(p*2, n+1, p)))

    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)

1.1499958793645562

可以做得更快吗？

此代码有一个缺陷：由于numbers是无序集，因此无法保证numbers.pop()从集中删除最小数字。然而，它对某些输入数字起作用（至少对我而言）：

>>> sum(get_primes(2000000))

142913828922L

#That's the correct sum of all numbers below 2 million

>>> 529 in get_primes(1000)

False

>>> 529 in get_primes(530)

True

Answer 1

更快，更内存的纯Python代码：def&nbsp;primes(n): &nbsp;&nbsp;&nbsp;&nbsp;"""&nbsp;Returns&nbsp;&nbsp;a&nbsp;list&nbsp;of&nbsp;primes&nbsp;<&nbsp;n&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;sieve&nbsp;=&nbsp;[True]&nbsp;*&nbsp;n&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(3,int(n**0.5)+1,2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;sieve[i]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;[2]&nbsp;+&nbsp;[i&nbsp;for&nbsp;i&nbsp;in&nbsp;range(3,n,2)&nbsp;if&nbsp;sieve[i]]或者从半筛开始def&nbsp;primes1(n): &nbsp;&nbsp;&nbsp;&nbsp;"""&nbsp;Returns&nbsp;&nbsp;a&nbsp;list&nbsp;of&nbsp;primes&nbsp;<&nbsp;n&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;sieve&nbsp;=&nbsp;[True]&nbsp;*&nbsp;(n//2) &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(3,int(n**0.5)+1,2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;sieve[i//2]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[i*i//2::i]&nbsp;=&nbsp;[False]&nbsp;*&nbsp;((n-i*i-1)//(2*i)+1) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;[2]&nbsp;+&nbsp;[2*i+1&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,n//2)&nbsp;if&nbsp;sieve[i]]更快，更内存的numpy代码：import&nbsp;numpydef&nbsp;primesfrom3to(n): &nbsp;&nbsp;&nbsp;&nbsp;"""&nbsp;Returns&nbsp;a&nbsp;array&nbsp;of&nbsp;primes,&nbsp;3&nbsp;<=&nbsp;p&nbsp;<&nbsp;n&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;sieve&nbsp;=&nbsp;numpy.ones(n//2,&nbsp;dtype=numpy.bool) &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(3,int(n**0.5)+1,2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;sieve[i//2]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[i*i//2::i]&nbsp;=&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;2*numpy.nonzero(sieve)[0][1::]+1从筛子的三分之一开始变化更快：import&nbsp;numpydef&nbsp;primesfrom2to(n): &nbsp;&nbsp;&nbsp;&nbsp;"""&nbsp;Input&nbsp;n>=6,&nbsp;Returns&nbsp;a&nbsp;array&nbsp;of&nbsp;primes,&nbsp;2&nbsp;<=&nbsp;p&nbsp;<&nbsp;n&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;sieve&nbsp;=&nbsp;numpy.ones(n//3&nbsp;+&nbsp;(n%6==2),&nbsp;dtype=numpy.bool) &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,int(n**0.5)//3+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;sieve[i]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k=3*i+1|1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k*k//3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;::2*k]&nbsp;=&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[k*(k-2*(i&1)+4)//3::2*k]&nbsp;=&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]上述代码的（难以编码）纯python版本将是：def&nbsp;primes2(n): &nbsp;&nbsp;&nbsp;&nbsp;"""&nbsp;Input&nbsp;n>=6,&nbsp;Returns&nbsp;a&nbsp;list&nbsp;of&nbsp;primes,&nbsp;2&nbsp;<=&nbsp;p&nbsp;<&nbsp;n&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;n,&nbsp;correction&nbsp;=&nbsp;n-n%6+6,&nbsp;2-(n%6>1) &nbsp;&nbsp;&nbsp;&nbsp;sieve&nbsp;=&nbsp;[True]&nbsp;*&nbsp;(n//3) &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,int(n**0.5)//3+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;sieve[i]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k=3*i+1|1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k*k//3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;::2*k]&nbsp;=&nbsp;[False]&nbsp;*&nbsp;((n//6-k*k//6-1)//k+1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sieve[k*(k-2*(i&1)+4)//3::2*k]&nbsp;=&nbsp;[False]&nbsp;*&nbsp;((n//6-k*(k-2*(i&1)+4)//6-1)//k+1) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;[2,3]&nbsp;+&nbsp;[3*i+1|1&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,n//3-correction)&nbsp;if&nbsp;sieve[i]]不幸的是，pure-python不采用更简单，更快速的numpy方式进行赋值，并且len()在循环内调用[False]*len(sieve[((k*k)//3)::2*k])太慢。所以我不得不即兴改正输入（避免更多的数学运算）并做一些极端（和痛苦）的数学魔术。就个人而言，我认为numpy（这是如此广泛使用）不是Python标准库的一部分是一种耻辱，并且Python开发人员似乎完全忽略了语法和速度的改进。