1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\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 '16 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\$ – Jared Mackey Apr 21 '16 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\$ – Joshua Dawson Apr 21 '16 at 20:17
  • \$\begingroup\$ @JoshDawson I just tested 4, and it doesn't for me. Could you show how? \$\endgroup\$ – Jamerack Apr 21 '16 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\$ – Joshua Dawson Apr 21 '16 at 20:42
2
\$\begingroup\$

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

This problem can be solved must 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 inclucing n**1/2:

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**1/2:
            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)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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