Hi, I was working on a solution to problem ten of Project Euler, which states:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

I've got code that solves this using eratosthenes sieve, but it loops painful though my total list:

def is_prime(Number):
    if Number == 1: return False
    elif Number == 2: return True
    elif not Number % 2: return False
    elif Number < 9 : return True
        n = 3
        while n < Number:
            if not Number % n:
                return False
                n += 2
    return True

def sum_primes(max_num):
    total = range(3, max_num+1, 2)
    for n in total:
        if is_prime(n):
            m = n+n
            t = 0
            while m < max(total): 
                t += 1
                    m += n
                except ValueError:
                    m += n
                if t == 1000:
                    print 'Looping though ' + str(n) + '; now at ' + str(m)
                    t = 0
    return sum([2] + total)

print sum_primes(2000000)

I'm not sure what is slowing this down so much. Thanks in advence!

2 Years
Discussion Span
Last Post by slate

Thank you, I apologize for my lack of understanding of the subject matter. Sometimes I find translating math into code a little blury, hence the optimization errors. I've looked into your link, and I didn't realize the sieve could be formaled into such a definte way. Since I don't have anything else to do, I feel up to hearing your analysis.

Just for fun, I added my checker into the script:

def eras(n, checker):
    siv = range(n+1)
    for i in range(2, sqn+1):
        if siv[i] != 0:
            siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
            if not siv[i] % checker:
                print 'Looping though the ' + str(siv[i]) + ' times table'
    return filter(None, siv)

print sum(eras(10, 1))

Edited by brett.warren.1612


I do not understand what your checker supposed to do semantically.
What are line 8 and 9 supposed to mean? Especially if you call it with 1.

If your algo is right, then all nonzero elements of the siv will be primes.

You can write a tests to check if the code works properly. Tests can be performed by using isprime function .

There is no use of testing the code on every run. The only case where this is appropriate, if some data is external or random. But that is not the case.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.