列出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
3 回答
慕姐4208626
TA貢獻1852條經驗 獲得超7個贊
更快，更內存的純Python代碼：
def primes(n): """ Returns a list of primes < n """ sieve = [True] * n for i in range(3,int(n**0.5)+1,2): if sieve[i]: sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1) return [2] + [i for i in range(3,n,2) if sieve[i]]
或者從半篩開始
def primes1(n): """ Returns a list of primes < n """ sieve = [True] * (n//2) for i in range(3,int(n**0.5)+1,2): if sieve[i//2]: sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1) return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
更快，更內存的numpy代碼：
import numpydef primesfrom3to(n): """ Returns a array of primes, 3 <= p < n """ sieve = numpy.ones(n//2, dtype=numpy.bool) for i in range(3,int(n**0.5)+1,2): if sieve[i//2]: sieve[i*i//2::i] = False return 2*numpy.nonzero(sieve)[0][1::]+1
從篩子的三分之一開始變化更快：
import numpydef primesfrom2to(n): """ Input n>=6, Returns a array of primes, 2 <= p < n """ sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool) for i in range(1,int(n**0.5)//3+1): if sieve[i]: k=3*i+1|1 sieve[ k*k//3 ::2*k] = False sieve[k*(k-2*(i&1)+4)//3::2*k] = False return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]
上述代碼的（難以編碼）純python版本將是：
def primes2(n): """ Input n>=6, Returns a list of primes, 2 <= p < n """ n, correction = n-n%6+6, 2-(n%6>1) sieve = [True] * (n//3) for i in range(1,int(n**0.5)//3+1): if sieve[i]: k=3*i+1|1 sieve[ k*k//3 ::2*k] = [False] * ((n//6-k*k//6-1)//k+1) sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1) return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
不幸的是，pure-python不采用更簡單，更快速的numpy方式進行賦值，并且len()在循環內調用[False]*len(sieve[((k*k)//3)::2*k])太慢。所以我不得不即興改正輸入（避免更多的數學運算）并做一些極端（和痛苦）的數學魔術。
就個人而言，我認為numpy（這是如此廣泛使用）不是Python標準庫的一部分是一種恥辱，并且Python開發人員似乎完全忽略了語法和速度的改進。
添加回答
舉報
0/150
提交
取消