Find primes using Sieve of Eratosthenes with Python I was Googling for a 'correct' or 'efficient' implementation of the Sieve of Eratosthenes. I found them all more complicated than what I came up with. I am by no means a Python expert, so I was wondering if something is wrong with my code.

def get_primes(max_int):
    numbers = range(2, max_int) 
    while len(numbers) &gt; 0:
        numbers = [ num for num in numbers if num % numbers[0] != 0 or num == numbers[0] ] # only keep numbers that are NOT divisible by the prime    
        yield numbers[0] # yield the prime
        numbers = numbers[1:] # make a new numbers-array, the first num is a new prime


Call it with 

primes = get_primes(1000)


And it gives you a generator of primes up until 1000.
Your code looks correct to me, it does produce prime numbers
in the given range. 

PEP8 Online reports some code style violations
with respect to whitespace and line length, but it is not too bad.

But: This is not the Sieve of Eratosthenes.
The Sieve of Eratosthenes keeps a (single) list of all candidate 
numbers, and computes multiples
of each found prime to mark subsequent composite numbers in the list.
Your algorithm computes the remainder of all remaining candidates instead, and creates new lists in each step.

As a simple benchmark I ran

print(sum(p for p in get_primes(100000)))


with your code, this takes approximately 5 seconds on my MacBook.

It can be improved slightly by filtering the list only once in
each step and not twice:

def get_primes(max_int):
    numbers = range(2, max_int)
    while len(numbers) &gt; 0:
        yield numbers[0]
        numbers = [num for num in numbers if num % numbers[0] != 0]


This reduces the time to 4.6 seconds.

But any “real” Eratosthenes sieve is much faster. As an example,
with this one
from Rosetta code

def primes_upto(limit):
    is_prime = [False] * 2 + [True] * (limit - 1) 
    for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
        if is_prime[n]:
            for i in range(n*n, limit+1, n):
                is_prime[i] = False
    return [i for i, prime in enumerate(is_prime) if prime]


the above benchmark runs in 0.08 seconds.