Project Euler #10 - summation of primes (From Project Euler)


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


Can someone please help me improve this code?

import math

def main():
    lim = 2000000
    i = 2
    now = []
    total = 0
    for i in range(2,lim+1):
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) ==2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
            print(total)
        now = []
    print(total)
First step : functions and tests

The very first thing you probably should write is a function computing what you really want : a sum of primes. Also, a value is provided as part of the problem, use this to write a test : as soon as something goes bad, you might notice it.

def sum_primes_to_limit(lim):
    i = 2
    now = []
    total = 0
    for i in range(2,lim+1):
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) ==2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
        now = []
    return(total)

def main():
    assert sum_primes_to_limit(10) == 17
    print(sum_primes_to_limit(2000000))


Making things simpler

Declaring the i variable is not needed.
Similarly, the now variable does not need to be defined before the loop and cleared at the end of each iteration : just define it as empty at each iteration.

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        now = []
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) == 2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
    return(total)


Making things even simpler

You don't really care about the content of now, just its length. Also, there's no need to check that it does not get longer that 2 at each iteration : just check when you update the list.

Also, you can get rid of the list and make it a simple counter :

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        nb_div = 0
        for x in range(1,int(math.sqrt(i))+1):
            if i % x == 0:
                nb_div += 1
                if nb_div == 2:
                    break

        if nb_div == 1:
            total += i
    return(total)


More function

Given the way you check if a number is prime or not, it probably make sense to define a function for this :

def is_prime(i):
    nb_div = 0
    for x in range(1,int(math.sqrt(i))+1):
        if i % x == 0:
            nb_div += 1
            if nb_div == 2:
                return False
    return nb_div == 1

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        if is_prime(i):
            total += i
    return(total)


A bit of Python cool syntax

Among the cool things in Python are generator expressions. Using generator expressions and sum, you can write sum_primes_to_limit in a concise and fancy way :

def sum_primes_to_limit(lim):
    return sum(i for i in range(2,lim+1) if is_prime(i))


Rewriting the function

You can avoid considering 1 as a divisor if you simply start at 2 (then, you might need some special processing for 1 but I'll leave this to you).

Then your function becomes :

def is_prime(i):
    nb_div = 0
    for x in range(2,int(math.sqrt(i))+1):
        if i % x == 0:
            nb_div += 1
            if nb_div == 1:
                return False
    return nb_div == 0


Then, you don't need the number anymore :

def is_prime(i):
    for x in range(2,int(math.sqrt(i))+1):
        if i % x == 0:
            return False
    return True


And this looks like it really wants to be written with generator expression (and all or any this time).

def is_prime(i):
    return all(i % x for x in range(2,int(math.sqrt(i))+1))


(Please note that I took this chance to remove a != 0 as non-zero boolean will evaluate to True).

This is all pretty cool but we want speed!

You want to compute/check primes up to a certain limit. Good for you there is an algorithm just for this : the Sieve of Eratosthenes.

Here's an implementation :

def sieve(lim):
    primes = [True] * (lim+1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(lim))+1):
        if primes[i]:
            for j in range(i*i, lim+1, i):
                primes[j] = False
    return primes

def sum_primes_to_limit(lim):
    primes = sieve(lim)
    return sum(i for i in range(2,lim+1) if primes[i])


Final details

I am used to Python 3 but if you are using Python 2, range generates an actual list. When this is not required (and in your case, this is not required), you should be using xrange.