4
\$\begingroup\$

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))
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why did you complicate the original print(sum(…)) with iter and list() and int() and the loop? \$\endgroup\$ – 200_success Jun 18 '16 at 13:27
  • 1
    \$\begingroup\$ print(sum(eratosthenes2(2000000))) could have been enough as said by @200_success why did you complicate so much? \$\endgroup\$ – Ja8zyjits Jun 18 '16 at 15:35
  • \$\begingroup\$ @Ja8zyjits Its just not the method I thought of first. Just because there is a "best" way to do it, doesn't guarantee it to be the first way I think of doing it. \$\endgroup\$ – MadisonCooper Jun 18 '16 at 15:41
  • 1
    \$\begingroup\$ well there are always a scope of improvement, instead of me or someone else adding an edit, i thought you may feel like doing it(if you dint think about that the first time.)[not a criticism but a suggestion though] \$\endgroup\$ – Ja8zyjits Jun 18 '16 at 16:05
6
\$\begingroup\$

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}\$.

\$\endgroup\$
  • \$\begingroup\$ I'm a little confused about your suggestion of a different approach. Can you expand on how you would check to see if a number is prime? Also, do you know how I can say remove every 2n, 3rd, etc item in a list? \$\endgroup\$ – Will Wang Jun 18 '16 at 2:07
5
\$\begingroup\$

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 ; 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(n3), which is very bad news when n = 2 000 000.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.