Speeding Up the Sieve of Eratosthenes With Numba

Lately, 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.