Here is a numba-ized version (using Numba 0.13) of your code this is optimized by using numpy arrays
import numpy as np
import numba
# You could also just use @numba.jit or @numba.jit(nopython=True)
# here and get comparable timings.
@numba.jit('void(uint8[:])', nopython=True)
def primes_util(sieve):
ssz = sieve.shape[0]
for j in xrange(ssz):
if sieve[j]:
new_prime = 2*j + 3
for k in xrange((2*j+6)*j+3, ssz, new_prime):
sieve[k] = False
def primes_numba(limit):
sieve = np.ones(limit // 2, dtype=np.uint8)
primes_util(sieve)
return [2] + (np.nonzero(sieve)[0]*2 + 3).tolist()
and then a comparison with timings:
In [112]: %timeit primes(LIMIT)
1 loops, best of 3: 221 ms per loop
In [113]: %timeit primes_numba(LIMIT)
100 loops, best of 3: 11 ms per loop
In [114]:
a = set(primes(LIMIT))
b = set(primes_numba(LIMIT))
a == b
Out[114]:
True
That's a 20x speedup, although there are probably even further optimization that could be made. Without the jit decorator, the numba version runs in about 300 ms on my machine. The actual call to primes_util
only takes about 5 ms and the rest is the call to np.nonzero
and the conversion to a list.