I'm doing a problem from Project Euler to find the sum of all primes under two million.

My code manages to get a pretty good result for small inputs, but when trying inputs like million or two it just won't finish.

import time
import math

def primes_sum(limit):
    num_list = range(2, limit)
    i, counter = 2, 1
    while i <= math.sqrt(limit):
        num_list = num_list[:counter] + filter(lambda x: x%i!=0, num_list[counter:])
        i = num_list[counter]
        counter +=1
    print sum(num_list)

def main():
    start_time = time.time()
    print 'Rum time: '+str(time.time()-start_time)

if __name__ == "__main__":

The error for 2 million:

Internal error: TypeError: FUNCTION_TABLE[HEAP[(HEAP[(c + 4)] + 28)]] is not a function
  • 1
    \$\begingroup\$ Given the puzzling error, this may be better suited to StackOverflow.se \$\endgroup\$
    – Caridorc
    Commented Aug 30, 2015 at 12:50
  • \$\begingroup\$ Should I create a new question there, or is there a way to move it there? \$\endgroup\$
    – galah92
    Commented Aug 30, 2015 at 12:55
  • \$\begingroup\$ I am not sure, let me ask @rolfl a moderator. Is this for CodeReview or StackOverflow or both? \$\endgroup\$
    – Caridorc
    Commented Aug 30, 2015 at 12:57
  • 1
    \$\begingroup\$ @Caridorc Normally, code with errors are off-topic in Code Review. However, I think we should allow this question since 1) it works for small limits, and 2) the error is to be addressed by improving the algorithm rather than by dissecting the error message. \$\endgroup\$ Commented Aug 30, 2015 at 19:06
  • \$\begingroup\$ @200_success Fair, does licensing allow me to post on StackOverflow asking about the error? It looks so weird.. \$\endgroup\$
    – Caridorc
    Commented Aug 30, 2015 at 19:08

2 Answers 2


Your primes_sum function seems to be inspired by the sieve of Erathostenes, but there are a number of things in your implementation that don't work out too well:

  • Do not remove items from you num_list. That's an expensive operation which basically requires rewriting the whole list. Plus, it makes the following point impossible.
  • If you have a list of consecutive integers, and you know the position i of a number n, you do not need to do modulo operations to figure out its multiples. Instead, repeatedly add n to i. Addition is much cheaper than modulo.
  • You don't actually need to have a list of numbers: instead keep a list of boolean values, with their position in the list indicating the number they represent. Ideally this would be a bit array, for maximal memory saving. But a list of Python booleans will save you 4 or 8 bytes per entry already.

A very straightforward implementation of a sieve would look like:

def sum_primes(n):
    sieve = [False, False] + [True] * (n - 1)  # 0 and 1 not prime
    for number, is_prime in enumerate(sieve):
        if not is_prime:
        if number * number > n:
        for not_a_prime in range(number * number, n+1, number): #If you use range(__, n, __), the function leaves the last Boolean in the sieve list as True, whether or not it is a prime. If you change it to range(__, n+1, __), this problem is taken care of. 
            sieve[not_a_prime] = False
    return sum(num for num, is_prime in enumerate(sieve) if is_prime)

On my system this spits the answer for 2 * 10^6 in under a second, manages to get 2 * 10^7 in a few, and can even produce 2 * 10^8 in well under a minute.

  • \$\begingroup\$ Super answer, thank you! Still I can't quite understand your implementation. I'm new to "enumerate" but think I understand what it created. So you looped over this sequence and for every prime number you found you.. looped again and deleted all it's multiples? Isn't it an expensive thing to to? \$\endgroup\$
    – galah92
    Commented Aug 31, 2015 at 17:38

You shouldn't end a function with print sum(num_list). It's much better to return sum(num_list) and then just use print primes_sum(2000000). If you ever want to use this for something else, it's much better having easy access to the number itself.

  • \$\begingroup\$ Beside the "use it afterwards" case, does it make any difference in terms of memory spending? \$\endgroup\$
    – galah92
    Commented Aug 31, 2015 at 17:40
  • \$\begingroup\$ @Gal Since you'd just be returning an int (rather than a list of the primes) the memory difference would be minimal. \$\endgroup\$ Commented Sep 1, 2015 at 14:46

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.