This Python snippet shows you how to take typical beginner's example of prime number function and work on improving its speed. The decorator function for timing is ideal tool to follow your progress you make. The improvements are commented and you are encouraged to make further improvements. Python is fun!
Prime Number Function Improvements (Python)
# time a number of progressively imrove prime number functions
# a decorator timing function is used
# declare the @decorator just above the function to invoke print_timing()
# tested with Python25 HAB 03feb2007
import time
def print_timing(func):
"""set up a decorator function for timing"""
def wrapper(*arg):
t1 = time.clock()
res = func(*arg)
t2 = time.clock()
print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)
return res
return wrapper
@print_timing
def get_primes1(r=10):
"""
unimproved original version
"""
primes = []
for i in range(2, r+1):
prime = 1
for divisor in range(2, i):
if i % divisor == 0:
prime = 0
break
if prime:
primes.append(i)
return primes
@print_timing
def get_primes2(r=10):
"""
improved version, loop only over odd numbers starting with 3
also limit the divisor range
"""
primes = [2]
# now ranges return odd numbers only ...
for i in range(3, r+1, 2):
prime = 1
for divisor in range(3, i//2, 2):
if i % divisor == 0:
prime = 0
break
if prime:
primes.append(i)
return primes
@print_timing
def get_primes3(r=10):
"""
improved version, loop only over odd numbers starting with 3
and limit devisor range even more
"""
primes = [2]
# now ranges return odd numbers only ...
for i in range(3, r+1, 2):
prime = 1
for divisor in range(3, i//7+3, 2):
if i % divisor == 0:
prime = 0
break
if prime:
primes.append(i)
return primes
@print_timing
def get_primes4(r=10):
"""
improved version, loop only over odd numbers starting with 3
and limit devisor range even more and using xrange()
"""
primes = [2]
# now ranges return odd numbers only ...
for i in xrange(3, r+1, 2):
prime = 1
for divisor in xrange(3, i//7+3, 2):
if i % divisor == 0:
prime = 0
break
if prime:
primes.append(i)
return primes
@print_timing
def get_primes5(r=10):
"""
improved version, loop only over odd numbers starting with 3
and limit devisor range further with **0.5 and using xrange()
"""
primes = [2]
# now ranges return odd numbers only ...
for i in xrange(3, r+1, 2):
prime = 1
for divisor in xrange(3, int(i ** 0.5)+1, 2):
if i % divisor == 0:
prime = 0
break
if prime:
primes.append(i)
return primes
@print_timing
def get_primes7(n):
"""
standard optimized sieve algorithm to get a list of prime numbers
--- this is the function to compare your functions against! ---
"""
if n < 2: return []
if n == 2: return [2]
# do only odd numbers starting at 3
s = range(3, n+1, 2)
# n**0.5 simpler than math.sqr(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m*m-3)//2 # int div
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i+1
m = 2*i+3
return [2]+[x for x in s if x]
r = 9000
p1 = get_primes1(r)
p2 = get_primes2(r)
p3 = get_primes3(r)
p4 = get_primes4(r)
p5 = get_primes5(r)
p7 = get_primes7(r)
# print the first 15 primes in the returned prime list for testing
print p1[:15]
print p2[:15]
print p3[:15]
print p4[:15]
print p5[:15]
print p7[:15]
print
# print the last 5 primes in the returned prime list for testing
print p1[-5:]
print p2[-5:]
print p3[-5:]
print p4[-5:]
print p5[-5:]
print p7[-5:]
"""
timing results for r=9000
get_primes1 took 2365.512 ms
get_primes2 took 467.231 ms
get_primes3 took 148.986 ms
get_primes4 took 104.222 ms
get_primes5 took 25.376 ms
get_primes7 took 2.483 ms
"""
bumsfeld 413 Nearly a Posting Virtuoso
Added sieve algorithm function to compare times with.
arkoenig 340 Practically a Master Poster
If you're going to generate a list of primes, rather than testing whether a single integer is prime, then why not use the list itself for the divisors?
TrustyTony 888 pyMod Team Colleague Featured Poster
If you're going to generate a list of primes, rather than testing whether a single integer is prime, then why not use the list itself for the divisors?
Ok here the more advanced alternatives:
from __future__ import print_function
import time
from math import sqrt, ceil
try:
import numpy as np
except:
print('No numpy')
def primes_np(n):
return []
# no numpy asume Python 3, no xrange
xrange = range
else:
def primes_np(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a array of primes, 2 <= p < n """
sieve = np.ones(n//3 + (n%6==2), dtype=np.bool)
sieve[0] = False
for i in xrange(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k] = False
sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
# for intensive use with non-numpy code we better transfer the format to standard int list
return map(int,np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)])
try:
import psyco
except:
print('No psyco available')
else:
psyco.full()
def rwh_primes1(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * (n//2)
for i in xrange(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 xrange(1,n//2) if sieve[i]]
def primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
# recurrence formula for length by amount1 and amount2 Tony Veijalainen 2010
""" Returns a list of primes < n """
sieve = [True] * (n//2)
amount1 = n-10
amount2 = 6
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i//2]:
## can you make recurrence formula for whole reciprocal?
sieve[i*i//2::i] = [False] * (amount1//amount2+1)
amount1-=4*i+4
amount2+=4
return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]
def get_primes(n):
"""
standard optimized sieve algorithm to get a list of prime numbers
--- this is the function to compare your functions against! ---
"""
if n < 2: return []
if n == 2: return [2]
# do only odd numbers starting at 3
s = list(xrange(3, n+1, 2))
# n**0.5 simpler than math.sqr(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m*m-3)//2 # int div
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i+1
m = 2*i+3
return [2]+[x for x in s if x]
def sieve_of_Atkin(end):
end += 1
lng = (end-1)>>1 # originally: lng = (end/2)-1+(end&1)
sieve = [False]*(lng + 1)
x_max, x2 = int(sqrt((end-1)/4.0)), 0
for xd in xrange(4, 8*x_max + 2, 8):
x2 += xd
y_max = int(sqrt(end-x2))
n = x2 + y_max*y_max
n_diff = (y_max << 1) - 1
if n&1 == 0: n -= n_diff; n_diff -= 2
for d in xrange((n_diff - 1) << 1, -1, -8):
m = n%12
if (m == 1 or m == 5):
m = n >> 1; sieve[m] = not sieve[m]
n -= d
x_max, x2 = int(sqrt((end-1)/3.0)), 0
for xd in xrange(3, 6*x_max + 2, 6):
x2 += xd
y_max = int(sqrt(end-x2))
n = x2 + y_max*y_max
n_diff = (y_max << 1) - 1
if n&1 == 0: n -= n_diff; n_diff -= 2
for d in xrange((n_diff - 1) << 1, -1, -8):
if (n%12 == 7):
m = n >> 1; sieve[m] = not sieve[m]
n -= d
x_max, y_min, x2, xd = int((2 + sqrt(4-8*(1-end)))/4), -1, 0, 3
for x in xrange(1, x_max + 1):
x2 += xd
xd += 6
if x2 >= end: y_min = (((int(ceil(sqrt(x2-end)))- 1) << 1)- 2) << 1
n = ((x*x + x) << 1) - 1
n_diff = (((x-1) << 1) - 2) << 1
for d in xrange(n_diff, y_min, -8):
if (n%12 == 11):
m = n >> 1; sieve[m] = not sieve[m]
n += d
primes = [2,3]; append= primes.append
if end <= 3 : return primes[:max(0,end-2)]
sqrtN = int(sqrt(end)) + 1
for n in xrange(2, sqrtN >> 1):
if sieve[n]:
i = (n << 1) +1; j=i*i; append(i)
for k in xrange(j, end, 2*j):
sieve[k>>1] = False
if sqrtN&1 == 0: sqrtN += 1
primes.extend([i for i in xrange(sqrtN, end, 2) if sieve[i >> 1]])
return primes
def SoZP5(val):
# all prime candidates > 5 are of form 30*k+(1,7,11,13,17,19,23,29)
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i = (n-3)>>1
n1, n2, n3, n4, n5, n6, n7, n8 = -1, 2, 4, 5, 7, 8, 10, 13
lndx = (val-1)>>1; sieve = [False]*(lndx+15)
while n8 < lndx:
n1 += 15; n2 += 15; n3 += 15; n4 += 15
n5 += 15; n6 += 15; n7 += 15; n8 += 15
sieve[n1] = sieve[n2] = sieve[n3] = sieve[n4] = \
sieve[n5] = sieve[n6] = sieve[n7] = sieve[n8] = True
# now initialize sieve with (odd) primes < 30
sieve[0] = sieve[1] = sieve[2] = sieve[4] = sieve[5] = \
sieve[7] = sieve[8] = sieve[10] = sieve[13] = True
n = 0; rescnt = 8
for i in xrange(2, ((int(sqrt(val))-3)>>1)+1, 1):
if not sieve[i]: continue
# p1=7*i, p2=11*i, p3=13*i --- p6=23*i, p7=29*i, p8=31*i, k=30*i
# j i 7i 11i 13i 17i 19i 23i 29i 31i 30i
# 7->2 23 37 44 58 65 79 100 107 105
j = (i<<1)+3; j2 = j<<1; p1 = j2+j+i; p2 = p1+j2; p3 = p2+j; p4 = p3+j2
p5 = p4+j; p6 = p5+j2; p7 = p6+j2+j; p8 = p7+j; k = p8-i
x = k*(n>>3)
n += 1 # x = k*(n/rescnt)
p1 += x; p2 += x; p3 += x; p4 += x; p5 += x; p6 += x; p7 += x; p8 += x
while p8 < lndx:
sieve[p1] = sieve[p2] = sieve[p3] = sieve[p4] = \
sieve[p5] = sieve[p6] = sieve[p7] = sieve[p8] = False
p1 += k; p2 += k; p3 += k; p4 += k; p5 += k; p6 += k; p7 += k; p8 += k
if p1 < lndx:
sieve[p1] = False
if p2 < lndx:
sieve[p2] = False
if p3 < lndx:
sieve[p3] = False
if p4 < lndx:
sieve[p4] = False
if p5 < lndx:
sieve[p5] = False
if p6 < lndx:
sieve[p6] = False
if p7 < lndx: sieve[p7] = False
if val < 3 : return [2]
if val < 5 : return [2,3]
primes = [(i<<1)+3 for i in xrange(2, lndx, 1) if sieve[i]]
primes[0:0] = [2,3,5]
return primes
if __name__ == '__main__':
numprimes=10**7
for test in (primes_np, rwh_primes1, primes, get_primes, sieve_of_Atkin, SoZP5):
t0= time.clock()
pr = test(numprimes)
t0 -= time.clock()
print(test.__name__, 'sum', sum(pr), 'time', -t0*1000, 'ms')
""" no psyco timings (Python 2.7.1):
No psyco available
primes_np sum 3203324994356 time 848.42263472 ms
rwh_primes1 sum 3203324994356 time 1851.15929539 ms
primes sum 3203324994356 time 1842.69648796 ms
get_primes sum 3203324994356 time 4751.71900339 ms
sieve_of_Atkin sum 3203324994356 time 5066.25283381 ms
SoZP5 sum 3203324994356 time 2690.95541472 ms
"""
""" psyco timings (2.6.6):
primes_np sum 3203324994356 time 852.706698756 ms
rwh_primes1 sum 3203324994356 time 1554.33693388 ms
primes sum 3203324994356 time 1500.75470486 ms
get_primes sum 3203324994356 time 3224.53579994 ms
sieve_of_Atkin sum 3203324994356 time 978.697571898 ms
SoZP5 sum 3203324994356 time 677.250320921 ms
""" Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.