# Speeding Up the Sieve of Eratosthenes With Numba

### In this post, we take a look at the Numba and NumPy libraries for Python and see how they help when performing calculations.

Join the DZone community and get the full member experience.

Join For FreeLately, upon invitation from my right honorable friend Michal, I've been trying to solve some problems from the Euler project and felt the need to have a good way to find prime numbers. So I implemented the the Sieve of Eratosthenes. The algorithm is simple and efficient. It creates a list of all integers below a number then filters out the multiples of all primes less than or equal to the square root of *n*, the remaining numbers are the eagerly-awaited primes. Here's the first version of the implementation I came up with:

```
def sieve_python(limit):
is_prime = [True]*limit
is_prime[0] = False
is_prime[1] = False
for d in range(2, int(limit**0.5) + 1):
if is_prime[d]:
for n in range(d*d, limit, d):
is_prime[n] = False
return is_prime
```

This returns a list *is_prime* where *is_prime[n]* is True *n* is a prime number. The code is straightforward but it wasn't fast enough for my taste so I decided to time it:

```
from timeit import timeit
def elapse_time(s):
s = timeit(s, number=100, globals=globals())
return f'{s:.3f} seconds'
print(elapse_time('sieve_python(100000)'))
```

`1.107 seconds`

1.1 seconds to check 100000 values indeed sounded too slow, so I decided to precompile the function with Numba:

```
from numba import njit
@njit
def sieve_python_jit(limit):
is_prime = [True]*limit
is_prime[0] = False
is_prime[1] = False
for d in range(2, int(limit**0.5) + 1):
if is_prime[d]:
for n in range(d*d, limit, d):
is_prime[n] = False
return is_prime
sieve_python_jit(10) # compilation
print(elapse_time('sieve_python_jit(100000)'))
```

`0.103 seconds`

The only addition to the previous version is the decorator `@njit`

and this simple change resulted in a whopping 10x speed up! However, Michal shared with me some code that made me notice that combining Numba with the appropriate NumPy data structures leads to impressive results; so this implementation materialized:

```
import numpy as np
@njit
def sieve_numpy_jit(limit):
is_prime = np.full(limit, True)
is_prime[0] = False
is_prime[1] = False
for d in range(2, int(np.sqrt(limit) + 1)):
if is_prime[d]:
for n in range(d*d, limit, d):
is_prime[n] = False
return is_prime
sieve_numpy_jit(10) # compilation
print(elapse_time('sieve_numpy_jit(100000)'))
```

`0.018 seconds`

The speed up respect to the first version is 61x!

Lessons learned:

- Using Numba is very straightforward and a Python function written in a decent manner can be speeded up with little effort.
- Python lists are too heavy in some cases. Even with pre-allocation of the memory, they can't beat NumPy arrays for this specific task.
- Assigning types correctly is key. Using a NumPy array of integers instead of bools in the function
`sieve_numpy_jit`

would result in a slow down.

Published at DZone with permission of Giuseppe Vettigli, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments