Trying to solve of Project Euler #10, but code takes *a lot* of time to display output

Question

Project Euler Problem 10:

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

Find the sum of all the primes below two million.

I don't think there is any errors in my code. But it takes really a lot of time to give the answer. I've tried using PyPy because I've heard its faster than the CPython interpreter, but still no good.

Here is the code:

#Implementation of Sieve of Eratosthenes
def prime_sieve(limit):
    primes = range(2, limit)
    for i in primes:
        for j in range(2, primes[-1]):
            try:
                primes.remove(i*j)
            except ValueError:
                pass

    return primes;


answer = 0

for x in prime_sieve(2000000):
    answer += x

print "Answer: %d." % answer
raw_input()

Answer 1

The right data structure for a prime sieve is a bitset, indexed by integer value. Python doesn't have one of those built-in, but since your limit is small (only 2 million), a regular list of integers should fit in memory even though its wasteful by a factor of 30 or more (it will take about 9 MB where the equivalent bitset in C would take 250 KB).

The important thing for speed is to never access the array except by immediate direct indexing (so no delete/remove). Also, limit the outer loop of the sieve to sqrt(limit), and advance the loop to the next prime, not the next value.

So something like this should be pretty quick (it take about 2 seconds on my old machine in vanilla Python 2.7).

import math, sys

def prime_sieve(limit):
    # Mark everything prime to start
    primes = [1 for x in xrange(limit)]
    primes[0] = 0
    primes[1] = 0

    # Only need to sieve up to sqrt(limit)
    imax = int(math.sqrt(limit) + 1)

    i = 2
    while (i < imax):
        j = i + i
        while j < limit:
            primes[j] = 0
            j += i

        # Move i to next prime
        while True:
           i += 1
           if primes[i] == 1:
               break

    return primes

s = prime_sieve(2000000)
print(sum(i for i in xrange(len(s)) if s[i] == 1))

Answer 2

The problem is this:

primes.remove(i*j)

.remove() is very inefficient when called on large lists, because it first has to iterate through the entire list to determine where, if any, the value is present, and then it has to iterate through a portion of the list again to shift all of the elements after the removed element down one spot.

There are other ways you could use data structures here (both other ways of using lists, and other data structures entirely) that would be more efficient.

Finally: your code modifies primes at the same time as you are iterating over it (which is what for i in primes is doing). This is generally considered a bad thing, since modifying something as it's being iterated over is potentially undefined behavior.

Answer 3

A more efficient idea goes like this:

You start with list:

[0,1,2,3,4,5,6,7,8,9,10]

You want to set every element that is not prime to 0, and keep the primes.

Set 0, and 1 to zero, because they are not primes. From now on you need to do these two steps:

1) Find the the smallest prime you have not considered yet, let's call it n

2) Set every nth element to 0 (but not n), since they are multiples of n

For example: after you set 0 and 1 to 0s:

[0,0,2,3,4,5,6,7,8,9,10]

The smallest prime you have not considered is 2, so you set every second element to zero (but not 2):

[0,0,2,3,0,5,0,7,0,9,0]

The smallest prime that you have not considered is 3, so you set every third element to zero (but not 3), and so on...:

[0,0,2,3,0,5,0,7,0,0,0]

Also notice, that you don't have to do this for every prime, once the primes have reached sqrt(limit) you can stop, because you know that all non-primes have been set to zeros.

For example, square root of 10(limit in this case) is 3.162, this means that we don't have to do anything when we get to 5 and we are done at that point. But why is that? We use each prime to set its multiples to zeros because those multiples are not primes; however, since 5 is larger than square root of 10, any multiple of 5 has to be a multiple of a number smaller than 5, and hence already has been set to 0.

Let's say that our initial range was from up to 20. Square root of 20 is less than 5 so we don't need to check for 5 because all multiples of 5: 5 * 2 = 10, 5 * 3 = 15, 5 * 2 * 2 = 20 are multiples of smaller primes, and we already set them to 0.

Answer 4

Here's a simple version of the Sieve of Eratosthenes adapted to compute the sum instead of forming a list of the primes less than n:

def sumPrimes(n):
    sum, sieve = 0, [True] * n
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

There are better ways to perform the sieving, but the function shown above is sufficient for this Project Euler problem; it should return the sum in about a second. If you're interested in programming with prime numbers, I modestly recommend this essay on my blog.

Answer 5

    def isPrime(n):
        if n < 2: return "Neither prime, nor composite"
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False
        return True



 def sumPrime():
        sumT = 0
        for i in range(2,2000000):
            if(isPrime(i)):
                sumT = sumT + i
        return sumT