Summation of primes takes forever Project Euler Problem 10 asks: "What is the sum of all prime numbers below 2 million?"

How do I speed up my code? It's taking forever and I have never gotten the answer. However, I am sure that my code is right; I cheated the answer from online as I couldn't wait for an hour.

def isPrime(number):

    for n in xrange (2,number):
        if number%n == 0:
            return False
    return True

result = 2

for k in xrange (3,2000000,2):
    if isPrime(k):
        result += k
        print result,"     ",k

print "The total is %d" % result


The result is 142913828922.
When the performance of your program in the face of large inputs is not even in the right ballpark, it's time to look for a new algorithm, even if your code is correct.  Factoring numbers is considered a "hard" problem — most public-key cryptography relies on the fact that factoring numbers takes a long time.

The Sieve of Eratosthenes would be perfect for this problem.  It should be possible in about 10 lines of code, and run in about one second.

Implementation hint:

# Build a big list
prime_list = range(limit + 1)

# Strike non-prime numbers 0 and 1 from the list
prime_list[0] = prime_list[1] = None

# TODO: Strike all multiples of prime numbers from the list
for k in xrange(len(prime_list)):
    ...

# Sum the numbers that have not been stricken out
return sum(filter(None, prime_list))


Alternatively, strike out numbers by setting them to 0 instead of None.  That removes the need to call filter(), but I think the clarity would suffer a tiny bit.