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

3 Answers 3


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__':


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]:
        if prime * prime > (end + 1):
        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])
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jamerack
    Apr 21, 2016 at 19:33
  • 2
    \$\begingroup\$ Please tell us why your piece of code is better, why did you chose this approach and so on. \$\endgroup\$ Apr 21, 2016 at 19:53
  • \$\begingroup\$ Oops excuse me I will write it more friendly :-) \$\endgroup\$ Apr 21, 2016 at 20:04
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 21, 2016 at 20:12
  • \$\begingroup\$ I am not so good at writing English excuse me :-( \$\endgroup\$ Apr 21, 2016 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
    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):
  • 1
    \$\begingroup\$ I think we should just use the math library anyway - edited appropriately. \$\endgroup\$ Feb 3, 2021 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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