Project Euler Problem 10

Question

Project Euler problem 10 is to find the sum of all primes less than 2 million. I have written a program that does this, and it works, but it takes an excruciatingly long amount of time. What I'm asking is if there is any way I could optimize this to make it run much faster.

I wrote it in an app on my iPad called Pythonista.

def checkPrime(number):
 if number == 2:
 return True
 if number < 2:
 return False
 if number % 2 == 0:
 return False
 for i in range(3, (number**1/2)-1, 2):
 if number % i == 0:
 return False
 return True
primes = [i for i in range(10000) if checkPrime(i)]
print sum(primes)

• Jamerack: @electrometro I was running it on my iPad, and it never actually finished running (I had left it running for about 20 mins), but I tried it with smaller values like 100000 and it worked fine, so I figured it would work with 2 million.
• Jared Mackey: Yeah it is taking a very long time. I didn't realize the value was incorrect for the loop. Checking now
• Joshua Dawson: I just noticed a bug in your code. Because you don't check the squareroot of n, numbers like 4, 9, 25 are getting counted as prime
• Jamerack: @JoshDawson I just tested 4, and it doesn't for me. Could you show how?
• Joshua Dawson: @Jamarack I tested it on the input '10' and got the result 26. 26 =わ 2 +たす 3 +たす 5 +たす 7 + (9)? 10 should return '17' Have you already submitted it to Project Euler?

Answer 1

This is a simple implementation of Sieve of Eratosthenes

#!/usr/bin/env python3
import unittest
import numpy as np
def sum_primes(end):
 is_prime = np.full(end+1, True, dtype=np.bool)
 is_prime[:2] = False
 for number, is_num_prime in enumerate(is_prime):
 if is_num_prime:
 is_prime[2*number::number] = False
 return np.arange(end+1)[is_prime].sum()
class TestSumOfPrimes(unittest.TestCase):
 def test_sum_primes(self):
 self.assertEqual(0, sum_primes(0))
 self.assertEqual(0, sum_primes(1))
 self.assertEqual(2, sum_primes(2))
 self.assertEqual(5, sum_primes(3))
 self.assertEqual(5, sum_primes(4))
 self.assertEqual(10, sum_primes(5))
 self.assertEqual(10, sum_primes(6))
 self.assertEqual(17, sum_primes(7))
 self.assertEqual(17, sum_primes(8))
 self.assertEqual(17, sum_primes(9))
 self.assertEqual(17, sum_primes(10))
 self.assertEqual(28, sum_primes(11))
 self.assertEqual(37550402023, sum_primes(1000000))
if __name__ == '__main__':
 unittest.main()

Update:

This version is friendlier:

def sum_primes(end):
 is_prime = [i not in [0, 1] for i in range(end+1)]
 for prime in range(end+1):
 if not is_prime[prime]:
 continue
 if prime * prime > (end + 1):
 break
 for multiple_of_prime in range(2*prime, end+1, prime):
 is_prime[multiple_of_prime] = False
 return sum(num for num in range(end+1) if is_prime[num])

• Jamerack: Thanks for the answer! I'm a relative beginner to Python and don't understand some of what is happening in your program, could you explain how it works? Particularly the stuff with unittest and numpy.
• Grajdeanu Alex: Please tell us why your piece of code is better, why did you chose this approach and so on.
• AmirHossein: Oops excuse me I will write it more friendly :-)
• AmirHossein: When you are using the naive algorithm for every number you are checking every single number before yourself and it gets almost huge when you repeat it for every number in a range! If you want to know if number n is prime you must check all n numbers before yourself to check whether it's prime or not. It's OK for a single number because you must check them anyway. But when you are looking for primes in a range, when you found a prime number you can cross out all of it's multiples and it reduces the number of elements you need to check.
• AmirHossein: I am not so good at writing English excuse me :-(

Answer 2

This problem can be solved much faster with a Sieve of Eratosthenes algorithm, especially since you need every prime between 2 and n for you to sum them up.

However, there are a few optimizations you could make to your particular algorithm.

---

Dynamic Programming

Your code preforms some redundant calculations. For example, once you've checked if n % 2 is zero, you know n % 4, n % 6... are also zero. To avoid these calculations you could instead divide by only the prime numbers up to and including √n:

primes = [2] #define your array of prime numbers
def checkPrime(number):
 if number < primes[0]:
 return False
 for p in primes: #only iterate through the primes
 if p > number**0.5:
 break; #no need to keep going
 if number % p == 0:
 return False
 
 primes.append(number);
 return True
primes = [i for i in range(10) if checkPrime(i)]
print sum(primes)

Answer 3

As others have said, you really want to be using a prime-generating sieve for this exercise.

A specific point in the code where you wrote something that's not what you meant is here:

for i in range(3, (number**1/2)-1, 2):

The ** operator has higher precedence than /, so number**1/2 actually means (number**1)/2, which is equal to number/2. You probably wanted number**(1/2) for a much smaller range. Better than that, the math library provides an integer square-root function, so let's use it:

for i in range(3, math.isqrt(number), 2):

• Toby Speight: I think we should just use the math library anyway - edited appropriately.