更快，更內(nèi)存的純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]]
更快，更內(nè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不采用更簡(jiǎn)單，更快速的numpy方式進(jìn)行賦值，并且len()在循環(huán)內(nèi)調(diào)用[False]*len(sieve[((k*k)//3)::2*k])太慢。所以我不得不即興改正輸入（避免更多的數(shù)學(xué)運(yùn)算）并做一些極端（和痛苦）的數(shù)學(xué)魔術(shù)。
就個(gè)人而言，我認(rèn)為numpy（這是如此廣泛使用）不是Python標(biāo)準(zhǔn)庫的一部分是一種恥辱，并且Python開發(fā)人員似乎完全忽略了語法和速度的改進(jìn)。
