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)

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

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