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 DZone.com Feed https://ift.tt/2uBwnL1