# Why does my implementation of the Sieve of Erastothenes take so long?

``````def sieve_of_erastothenes(number):
"""Constructs all primes below the number"""
big_list = [2] + range(3, number+1, 2)  # ignore even numbers except 2
i = 1  # start at n=3, we've already done the even numbers
while True:
try:
# use the next number that has not been removed already
n = big_list[i]
except IndexError:  # if we've reached the end of big_list we're done here
return big_list
# keep only numbers that are smaller than n or not multiples of n
big_list = [m for m in big_list if m<=n or m%n != 0]
i += 1
``````

On my computer, this code takes about half a second to calculate all primes below 10,000, fifteen seconds to do 100,000, and a very long time to calculate primes up to one million. I'm pretty sure it's correct (the first few numbers in the returned sequence are right), so what can I do to optimise it?

I've tried a version that removes the relevant numbers in-place but that takes even longer (since it takes O(n) to move all the remaining numbers down).

-
I know this could do with more tags but I'm not allowed to create them –  Benjamin Hodgson Sep 20 '12 at 22:36
I'm not very familiar with Python, but I might try using an array of i -> true/false (true meaning it's a prime, false meaning it's not). Your code would then go over this array and mark numbers as non-prime. I think your large growth in time is coming from copying the modified list over and over again. If you modify an array in place (modify the values, not remove them) and then generate a list based on that, I have a very strong hunch that it will be faster. –  Corbin Sep 21 '12 at 5:01
add comment

## 2 Answers

The problem is that the way this is set up, the time complexity is (close to) O(n**2). For each remaining prime, you run over the entire list.

In the last case, where you want to check for prime numbers up to 1,000,000 you end up iterating over your list 78,498 ** 2 times. 6,161,936,004 iterations is a lot to process.

Below is an approach that crosses off the numbers instead, editing the large list of numbers in-place. This makes for a O(n) solution, which times as such:

• range 10,000 : 549 usec per loop
• range 100,000 : 14.8 msec per loop
• range 1,000,000: 269 msec per loop
• range 10,000,000: 3.26 sec per loop

``````def sieve_of_erastothenes(limit):
"""Create a list of all numbers up to `number`, mark all non-primes 0,
leave all the primes in place. Filter out non-primes in the last step.
"""
sieve = range(limit + 1)

# There are no prime factors larger than sqrt(number):
test_max = int(math.ceil(limit ** 0.5))

# We know 1 is not a prime factor
sieve[1] = 0

# The next is a cheat which allows us to not even consider even numbers
# in the main loop of the program. You can leave this out and replace the
# current xrange(3, test_max, 2) with xrange(2, test_max)

# All multiples of 2 are not prime numbers, except for 2 itself:
sieve[4::2] = (limit / 2 - 1) * [0]

for prime in xrange(3, test_max, 2):
if sieve[prime]:
# If the number hasn't been marked a composite, it is prime.
# For each prime number, we now mark its multiples as non-prime.
multiples_count = limit / prime - (prime - 1)
sieve[prime * prime::prime] = multiples_count * [0]
# Filter out all the zeroes, we are left with only the primes
return filter(None, sieve)
``````
-
add comment

There are links to much faster python implementations from this post: Sieve of Eratosthenes: making it quicker

You can compare many different implementations at http://ideone.com/5YJkw, with the fastest one that was cited from the other post being available at http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188

-
add comment