Project Euler 10: find the sum of all the primes below two million

Question

This is question #10 from Project Euler:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.

I just started programming and read that a Sieve of Eratosthenes is the fastest way to find primes however this code is taking forever to run. How can I make this go faster?

end = False
all = list(range(2, 2000000))
delnum = 2
while all.index(delnum)+1 <= len(all) and end == False:
    for x in all:
        if x % delnum == 0 and delnum != x:
            all.remove(x)
    if all.index(delnum)+1 == len(all):
        end = True
    if all.index(delnum)+1 <= len(all) and end == False:
        delnum = all[all.index(delnum) + 1]
print(sum(all))

Answer 1

Building off of what Grigory Ilizirov mentioned about the code staying in the all.remove() part for a significant amount of time here is a page with many different implementations of the Sieve in many different languages. You should start out at the Most efficient python implementation by clicking this link.

The set method is CRAZY fast. Mainly because of the 'if i not in multiples(the set)' part. set() has a very efficient way of searching for an element called a hash function. Now, how exactly python implements that is beyond me. I've seen this example (2nd comment, not the accepted one).

To quote it here:

list: Imagine you are looking for your socks in your closet, but you don't know in which drawer your socks are, so you have to search drawer by drawer until you find them (or maybe you never do). That's what we call O(n), because in the worst scenario, you will look in all your drawers (where n is the number of drawers).

set: Now, imagine you're still looking for your socks in your closet, but now you know in which drawer your socks are, say in the 3rd drawer. So, you will just search in the 3rd drawer, instead of searching in all drawers. That's what we call O(1), because in the worst scenario you will look in just one drawer. - juliomalegria

Running:

def eratosthenes2(n):
    #Declare a set - an unordered collection of unique elements
    multiples = set()

    #Iterate through [2,2000000]
    for i in range(2, n+1):

        #If i has not been eliminated already 
        if i not in multiples:

            #Yay prime!
            yield i

            #Add multiples of the prime in the range to the 'invalid' set
            multiples.update(range(i*i, n+1, i))

#Now sum it up
iter = 0
ml = list(eratosthenes2(2000000))
for x in ml:
    iter = int(x) + iter

print(iter)

Completed almost before I could get my finger off of the 'run' button.

Answer 2

Most of the time the line all.remove(x) is running, and it is executed for all non-prime numbers, which is most of the numbers.

Moreover, your remove items by value, which means that each time you remove it, a searching by value is performed on the list, making it even slower.

You can avoid this if, instead of removing the non-primes, you

1. set zero in their place and access the list by index
2. build a list for collecting the identified primes

But I would suggest a completely different approach:

Instead of starting with list of all numbers all = list(range(2, 2000000)), and then removing the non-primes, it is better just start with empty list and adding the number if it is prime. Or if you need only the sum, don't save the primes at all; just sum them.

if you want to check if the number \$n\$ is prime, you don't need to check division for all the numbers. Check only from 2 to \$\sqrt{n}\$.

Answer 3

Flag variables like end are poor style. Setting a variable so that some other code can check it and exit the loop is cumbersome. If you want to break out of the loop, just write break.

Avoid naming variables the same as built-in functions. Pick a different name instead of all.

Applying those two changes:

numbers = list(range(2, 2000000))
delnum = 2
while numbers.index(delnum)+1 <= len(numbers):
    for x in numbers:
        if x % delnum == 0 and delnum != x:
            numbers.remove(x)
    if numbers.index(delnum)+1 == len(numbers):
        break
    if numbers.index(delnum)+1 <= len(numbers):
        delnum = numbers[numbers.index(delnum) + 1]
print(sum(numbers))

numbers.index(delnum) + 1 <= len(numbers) will always be True (or it could crash with a ValueError, which shouldn't be possible here). So, the code is just…

numbers = list(range(2, 2000000))
for prime in numbers:
    for x in numbers:
        if x % prime == 0 and prime != x:
            numbers.remove(x)
print(sum(numbers))

That is not only a simplification, it's also a performance improvement, since we have eliminated all of the .index() calls (each of which involves a linear search of the list).

However, this algorithm is not the sieve-of-eratosthenes; it's much slower. In particular, the Sieve of Eratosthenes involves no division or modulo operations. It also does not involve .remove() operations, which are slow because they involve a linear search of the list to find the element to remove, then copying all subsequent elements to fill in the hole left by the removal. Since the outer loop is O(n), the inner loop is O(n), and numbers.remove() is O(n), this "improved" solution is still O(n³), which is very bad news when n = 2 000 000.