Sieve of Eratosthenes in Python This is yet another take in Python for the infamous Sieve of Eratosthenes. I am a beginner in Python so any criticism is highly appreciated. 

# Find primes until this integer.. Modify to your taste..
upper_bound = 1000

# Pass a list of integers and a prime number, 
# will return you a list where numbers divisible by the prime you passed are removed.
def remove_non_primes(list_of_ints, prime_to_check_against):
    multiplier = 1
    while prime_to_check_against * multiplier &lt; list_of_ints[-1]:
        multiplier += 1
        # Should be quite fast since list is sorted.
        if prime_to_check_against * multiplier in list_of_ints:
            list_of_ints.remove(prime_to_check_against * multiplier)
    return list_of_ints


ints = list(range(2, upper_bound)) # Generate initial list of integers

# Initial prime for bootstrap
prime = 2 
# Keep track of iteration count, so we know the next prime to work with in each iteration.
iteration_count = 0 

while True:
    # Use length of list to determine we removed everything we could by 
    # checking this length against returning lists length.
    original_list_length = len(ints)
    # Do the magic, remove all non primes found by parameter prime.
    ints = remove_non_primes(ints, prime)
    # List was not modified.. Nothing to remove.
    if original_list_length == len(ints): 
        break
    iteration_count += 1
    prime = ints[iteration_count]

print(ints)


Are there any modifications that will dramatically increase the performance?
I question the following comment:

    # Should be quite fast since list is sorted.
    if prime_to_check_against * multiplier in list_of_ints:
        list_of_ints.remove(prime_to_check_against * multiplier)


Why will this be fast, due to the sorted list?  x in list doesn't understand that the list is sorted, nor does the remove(x).  No binary searching will be done; just a straight linear search.  Not fast.



I also question the following comment:

    # List was not modified.. Nothing to remove.
    if original_list_length == len(ints): 
        break


Just because no multiples of 29 may remain in the list does not necessarily mean there are no multiples of 31!  The proper stopping condition is when you reach sqrt(upper_bound).



You are attempting to remove numbers you've already removed:

multiplier = 1
while prime_to_check_against * multiplier &lt; list_of_ints[-1]:
    multiplier += 1
    if prime_to_check_against * multiplier in list_of_ints:
        list_of_ints.remove(prime_to_check_against * multiplier)


When you remove multiples of 13, for instance, you are starting by removing 13*2, and 13*3, and 13*4, and so on.

But you have already removed all the multiples of primes lower than 13.  You should start at 13*13,

    multiplier = prime_to_check_against
    while prime_to_check_against * multiplier &lt;= list_of_ints[-1]:
        if prime_to_check_against * multiplier in list_of_ints:
            list_of_ints.remove(prime_to_check_against * multiplier)
        multiplier += 1




Finding and then removing.  You are searching the list twice: once to check if it exists, a second time to find it in order to remove it.

Instead, you could simply removed the item.

    try:
        list_of_ints.remove(prime_to_check_against * multipler)
    except ValueError:
        pass # it wasn't there




Even numbers as a special case.

ints = [2] + list(range(3, upper_bound, 2)) # Generate initial list of odd integers

# Initial prime for bootstrap
prime = 3
iteration_count = 1


And then, instead of increasing the multiplier by 1, you can increase it by 2, so you'd search 13*13, 13*15, 13*17, ...

        multiplier += 2




Skip all of the multiplications, and just increment by 2*prime_to_check_against

    multiple  = prime_to_check_against * prime_to_check_against
    increment = prime_to_check_against * 2 
    while multiple &lt;= list_of_ints[-1]:
        try:
            list_of_ints.remove(multiple)
        except ValueError:
            pass
        multiple += increment


Or more pythonically:

    for multiple in range(prime_to_check_against * prime_to_check_against,
                          list_of_ints[-1]+1, 2*prime_to_check_against):
        try:
            list_of_ints.remove(multiple)
        except ValueError:
            pass




Instead of populating a list with all of the candidate numbers, and then removing multiples of prime numbers from the list, which involves expensive list manipulations, you could:


create a bytearray(upper_bound) to store prime/not-prime flags
flag all multiples of prime numbers, as you find them, as not-prime
use list-comprehension to extract the indexes which are flagged as prime


Using a bytearray is very efficient memory-wise, and indexing into the bytearray to set or test a flag is a very fast \$O(1)\$ operation.

I'm trying to decide whether to post my 10-lines of code for the sieve here, or let you attempt it based on the above hints.  Let me know if you need it.