8
\$\begingroup\$

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()
    primes_sum(2000000)
    print 'Rum time: '+str(time.time()-start_time)

if __name__ == "__main__":
    main()

The error for 2 million:

Internal error: TypeError: FUNCTION_TABLE[HEAP[(HEAP[(c + 4)] + 28)]] is not a function
\$\endgroup\$
  • 1
    \$\begingroup\$ Given the puzzling error, this may be better suited to StackOverflow.se \$\endgroup\$ – Caridorc Aug 30 '15 at 12:50
  • \$\begingroup\$ Should I create a new question there, or is there a way to move it there? \$\endgroup\$ – galah92 Aug 30 '15 at 12:55
  • \$\begingroup\$ I am not sure, let me ask @rolfl a moderator. Is this for CodeReview or StackOverflow or both? \$\endgroup\$ – Caridorc Aug 30 '15 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\$ – 200_success Aug 30 '15 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 Aug 30 '15 at 19:08
8
\$\begingroup\$

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:
            continue
        if number * number > n:
            break
        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.

\$\endgroup\$
  • \$\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 Aug 31 '15 at 17:38
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Beside the "use it afterwards" case, does it make any difference in terms of memory spending? \$\endgroup\$ – galah92 Aug 31 '15 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\$ – SuperBiasedMan Sep 1 '15 at 14:46

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.