Sieve of Eratosthenes in Python

Question

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 < 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?

• Heslacher: I have rolled back your lastedit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .

Answer 1

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 < 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 <= 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 <= 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.

• Koray Tugay: Even numbers as a special case: Very good suggestion thank you, but I think Exception Handling is quite expensive, isnt it?
• Koray Tugay: What do you mean When you remove 13? I never remove 13..
• AJNeufeld: Sorry - when you remove multiples of 13.
• AJNeufeld: No; exception handling in Python is very cheap. "It is better to try and ask forgiveness than to ask for permission" is a common idiom in Python for this reason.
• Koray Tugay: Excellent answer, thank you. I will start a bounty just to give you more rep, but need a few days, cant start immediately. Thanks again.