def sieve_unoptimized(n):
grains = [True]*n
for i in range(2, len(grains)):
ri = i*2
while ri < len(grains):
grains[ri] = False
ri += i
return zip(*filter(lambda (x, y): y, list(enumerate(grains))))[0][1:]
sieve_unoptimized(30)
(1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
import math
def sieve_optimized(n):
grains = [True]*n
for i in range(2, int(math.sqrt(len(grains)))+1):
ri = i**2
while ri < len(grains):
grains[ri] = False
ri += i
return zip(*filter(lambda (x, y): y, list(enumerate(grains))))[0][1:]
sieve_optimized(30)
(1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
import numpy as np
def sieve_np_optimized(n):
grains = np.ones(n)*True
for i in np.arange(2, int(np.sqrt(grains.shape[0])) + 1):
grains[i**2::i] = False
return np.where(grains)[0][1:]
sieve_np_optimized(30)
array([ 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
%timeit sieve_unoptimized(15485863)
1 loops, best of 3: 41.7 s per loop
%timeit sieve_optimized(15485863)
1 loops, best of 3: 20.4 s per loop
%timeit sieve_np_optimized(15485863)
1 loops, best of 3: 979 ms per loop
d = sieve_np_optimized(15485863)
len(d)
1000000
%pylab inline
Populating the interactive namespace from numpy and matplotlib
step(np.arange(len(d)-1), np.diff(d))
[<matplotlib.lines.Line2D at 0x45dc7bcc>]