﻿ Fast Prime List Functions_python_开心洋葱网
• 欢迎访问开心洋葱网站，在线教程，推荐使用最新版火狐浏览器和Chrome浏览器访问本网站，欢迎加入开心洋葱` QQ群`
• 为方便开心洋葱网用户，开心洋葱官网已经开启复制功能！
• 欢迎访问开心洋葱网站，手机也能访问哦~欢迎加入开心洋葱多维思维学习平台` QQ群`
• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~！
• 由于近期流量激增，小站的ECS没能经的起亲们的访问，本站依然没有盈利，如果各位看如果觉着文字不错，还请看官给小站打个赏~~~~~~~~~~~~~！

# Fast Prime List Functions

3117次浏览

There is always room for optimizing primelist functions. Here is an assortment timed with Python module timeit …

```'''primelist_timing1.py
timing some very fast primelist functions
tested with Python27 and Python32  by  vegaseat
'''
import timeit
import numpy
import sys
print("Python version:\n %s\n" % sys.version)
def time_function(stmt, setup):
"""
use module timeit to time functions
"""
# to enable garbage collection start setup with 'gc.enable();'
#setup = 'gc.enable();' + setup
t = timeit.Timer(stmt, setup)
times = 10000
num = 100
# times*num has to be 1000000 to get time in microseconds/pass
# (lower num is a little less precise but saves time)
elapsed = (times * t.timeit(number=num))
print("%-20s --> %0.2f microseconds/pass" % (stmt, elapsed))
def primelist_bw(n):
"""
returns  a list of primes < n
by Bill Woods
"""
sieve = [True] * (n>>1)
for x in range(3, int(n**0.5)+1, 2):
if sieve[x>>1]:
sieve[x*x//2::x] = [False] * ((n-x*x-1)//(x<<1)+1)
return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]
def primelist_ds(n):
"""
returns  a list of primes < n
"""
sieve = [True] * (n>>1)
for x in range(3, int(n**0.5)+1, 2):
if sieve[x>>1]:
sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]
def primes_numpy(n):
"""
requires module numpy and n>=6,
returns a list of primes 2 <= p < n
"""
sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
sieve[0] = False
for x in range(int(n**0.5)//3+1):
if sieve[x]:
k = 3*x + 1|1
sieve[((k*k)//3)::2*k] = False
sieve[(k*k+4*k-2*k*(x&1))//3::2*k] = False
return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0]+1)|1)].tolist()
# time a function
stmt = 'primelist_bw(1000000)'
setup = 'from __main__ import primelist_bw'
time_function(stmt, setup)
# time a function
stmt = 'primelist_ds(1000000)'
setup = 'from __main__ import primelist_ds'
time_function(stmt, setup)
# time a function
stmt = 'primes_numpy(1000000)'
setup = 'from __main__ import primes_numpy, numpy'
time_function(stmt, setup)
print('-'*60)
# additional test (show the last 5 primes) ...
print(primelist_bw(1000000)[-5:])
print(primelist_ds(1000000)[-5:])
print(primes_numpy(1000000)[-5:])
'''result ...
Python version:
2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)]
primelist_bw(1000000) --> 75969.22 microseconds/pass
primelist_ds(1000000) --> 73669.90 microseconds/pass
primes_numpy(1000000) --> 9016.74 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
Python version:
3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)]
primelist_bw(1000000) --> 77284.28 microseconds/pass
primelist_ds(1000000) --> 75547.38 microseconds/pass
primes_numpy(1000000) --> 28055.11 microseconds/pass
------------------------------------------------------------
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
[999953, 999959, 999961, 999979, 999983]
'''
```