# Project Euler Problem 10

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)

• @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. Apr 21 '16 at 19:24
• Yeah it is taking a very long time. I didn't realize the value was incorrect for the loop. Checking now Apr 21 '16 at 19:26
• 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 Apr 21 '16 at 20:17
• @JoshDawson I just tested 4, and it doesn't for me. Could you show how? Apr 21 '16 at 20:19
• @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? Apr 21 '16 at 20:42

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])

• 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. Apr 21 '16 at 19:33
• Please tell us why your piece of code is better, why did you chose this approach and so on. Apr 21 '16 at 19:53
• Oops excuse me I will write it more friendly :-) Apr 21 '16 at 20:04
• 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. Apr 21 '16 at 20:12
• I am not so good at writing English excuse me :-( Apr 21 '16 at 20:13

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)


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):

• I think we should just use the math library anyway - edited appropriately. Feb 3 '21 at 13:01