Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
Srry, Edited and improved a bit. –  Dark Mirror Dec 16 '13 at 23:17
1  
One tip: Replace your implementation of isPrime(number) with the Miller Rabin primality test. It will be much faster. –  Darren Stone Dec 17 '13 at 2:41
add comment

3 Answers 3

up vote 2 down vote accepted

Here's a simple function that should give the answer pretty quickly:

def sum_primes(limit):
    primes = []
    for n in xrange(2, limit+1):
        # try dividing n with all primes less than sqrt(n):
        for p in primes:
            if n % p == 0: break     # if p divides n, stop the search
            if n < p*p:
               primes.append(n)      # if p > sqrt(n), mark n as prime and stop search
               break
        else: primes.append(n)       # fallback: we actually only get here for n == 2
    return sum(primes)

It relies on the fact that every composite number n must be divisible by a prime p less than or equal to its square root. (Proof: By definition, every composite number is divisible by some prime. If n is divisible by a prime p > sqrt(n), then n is also divisible by m = n / p < sqrt(n), and thus n must be divisible by some prime divisor qm < sqrt(n) of m.)

The only tricky part, performance-wise, is ensuring that we don't iterate through the list of primes any further than necessary to confirm or deny the primality of n. For this, both of the breaking conditions are important.

The code above is actually somewhat inefficient in its memory use, since it builds up the entire list of primes up to the limit before summing them. If we instead maintained a running sum in a separate variable, we wouldn't need to store any of the primes above the square root of the limit in the list. Implementing that optimization is left as an exercise.


Edit: As 200_success suggests, a well-written Sieve of Eratosthenes can indeed be faster than the trial division method described above, at the cost of using more memory. Here's an example of such a solution:

from math import sqrt
def sum_primes(limit):
    sieve = range(limit+1); sieve[1] = 0
    for n in xrange(2, int(sqrt(limit))+1):
        if sieve[n] > 0:
            for i in xrange(n*n, limit+1, n): sieve[i] = 0
    return sum(sieve)

On my computer, this runs nice and fast for a limit of 2 million or 20 million, but throws a MemoryError for 200 million.

share|improve this answer
    
This is amazingly fast too. –  Dark Mirror Dec 17 '13 at 3:06
2  
This is the first time I've seen an "else" block to a "for" loop. –  ShreevatsaR Dec 17 '13 at 7:53
1  
Me too, but it makes sense. stackoverflow.com/questions/9979970/… –  Alexios Dec 17 '13 at 8:36
    
I see what you mean now by iterating up to sqrt(limit) + 1) in the Sieve of Eratosthenes. –  200_success Dec 17 '13 at 8:53
1  
A common improvement is to skip even numbers. primes=[2]; for n in xrange(3, limit+1, 2): ... –  ejrb Dec 17 '13 at 9:26
add comment

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.

share|improve this answer
    
Awesome, let me try it... –  Dark Mirror Dec 16 '13 at 23:55
add comment

Unfortunately, I don't speak python so I can't provide any code but there's a couple of things I see that can be improved algorithmically:

  1. In isPrime start checking if it's divisible by two, then start check 3 and increase by two on each step. So instead of checking 2,3,4,5,6... you check 2,3,5,7,9,11,13,15...
  2. You only need to check numbers up to sqrt(number) in your isPrimes method

Point 1 here can also be applied to your main loop (that goes from 2 to 20000000). Initialize k to 2 and check if that's prime. Then set k to 3, check if it's prime and then increase k by 2 each time. So that the numbers you check for primeness also becomes 2,3,5,7,9,11...

Theory on another approach (Untested in all languages, might not work)

I'm not sure if this will be faster or not, but here's a thought that you might be able to gain speed with:

Since you loop through numbers to check for primes, add the already found primes to a list and when checking a new number then you only need to check if it's divisible by one of the previously known primes. That way you won't have to check with 9 and 15 for example.

Pseudo-code:

  1. Create an empty list, here called primeList
  2. Loop from 2 to 2000000, call this number k (as in your existing code)
  3. Check if the number is divisible by any item in the primeList, if it is then k is not prime so go to the next iteration.
  4. If a number was not found in step 3, then add k to the primeList
share|improve this answer
4  
Your other approach is basically an inefficient implementation of the sieve of Erathostenes. So while it can be done better, your idea will replace having to do n checks to test n for primality, to only do about n / log(n), so it is definitely going to be (much) faster. –  Jaime Dec 16 '13 at 23:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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