Implementing Sieve of Eratosthenes faster I wrote a version of sieve of eratosthenes:

number =100000000
def eratos_sieve(n:"find prime below this"=None):
        if not(n):
            n = number
        numbers = [x for x in range(0, n+1)]
        current_prime = 2
        sqrt_limit = int(math.sqrt(n))+1
        while numbers[current_prime] &lt;= sqrt_limit:
            #(len(numbers)-1) is the actual size since
            #since, len([0,...,n])=n+1
            for i in range(current_prime, ((len(numbers)-1)//current_prime)+1):
                numbers[current_prime*i]=-1
            current_prime += 1
            for i in range(current_prime, sqrt_limit):
                if numbers[i]&gt;0:
                    current_prime=i
                    break


        #this part is optional
        j = 0
        for i in range(len(numbers)):
            if numbers[i]&gt;0:
                numbers[j]=numbers[i]
                j += 1
        #uptil here if later primes are to be found using indices
        #else all primes upto n are returned as a single list
        return numbers[1:j]


It seems to perform fast enough for my purposes. I'd like to get some review about it's performance since I'm a novice. Also, I'd like someone with enough memory (if possible) to run the below two tests:

import time
import math
num1 = 100000000 #100 million
num2 = 1000000000 #1 billion
start = time.perf_counter()
eratos_sieve(num1)
total_100_m = time.perf_counter()-start()

start = time.perf_counter()
eratos_sieve(num2)
total_1_b = time.perf_counter()-start()

print("For 100m it takes: ", total_100_m)
print("For 1b   it takes: ", total_1_b)
Four* letters to rule them all

The Sieve of Eratosthenes is an algorithm which heavily relies on loops. Unfortunately, Python's convenient scripty nature comes at a cost: it's not terribly fast when it comes to loops, so it's best to avoid them.

However, this is not always possible, or one, like me in this case, is not so much into algorithms to transform them into another form. Enter numba. numba is a just-in-time compiler for Python code. The just-in-time compiler can transform plain Python code into "native" code for your system. So what are those magical four letters I was talking about? It's @jit. 

This simple decorator and no further code changes brought the time for n = 100 000 000 from 36s down to about 3s on my machine. The larger test case did not work out to well with my 16GB RAM and some other things to do apart from Code Review.

from numba import jit

@jit
def eratos_sieve(n:"find prime below this"=100000000):
    # ... the rest of your code here


You can also have a look at this generator based implementation of the algorithm presented on Stack Overflow. The implementation can benefit from just-in-time compilation as well. A quick test using the SO approach and @jit for the previous n brought the execution time down to just below 2s on the same machine as before.

What numba cannot fix for you

There are a few aspects with respect to style and idiomatic language features (often called pythonic code) that you have to/can improve yourself.

While 

number =10000000
def eratos_sieve(n:"find prime below this"=None):
    if not(n):
        n = number
    ...


might be working and syntactically valid, I find it very, very uncommon and would not recommend it. A more "pythonic" way to express this would be

def eratos_sieve(n: int = 100000000):
    """Find all primes below a given whole number n"""
    ...


This makes use of Python 3's type hinting and the recommended way to write function documentation using docstrings.

The way you construct your candidate list using numbers = [x for x in range(0, n+1)] is also a little bit complicated, and may be simplified to numbers = list(range(n+1)). 0 is the implicit starting value for range(...) and since range(...) already returns a generator you can simply pass it to a list constructor and work with it.

You should also have a look at the official Style Guide for Python Code (PEP8) and follow it's recommendations regarding whitespace within expressions and statements.

If you intend to supply your testing code together with your function in a single script, wrap it in the well known if __name__ == "__main__": construct to ensure it is only run if your code is used as a script.



* Well not strictly speaking, but it's close.