# 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.

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)

• Take a look at this – OMGtechy Sep 2 '14 at 15:28
• You're running through the same numbers every time you evaluate a new i. Perhaps a method that only loops once can be implemented wink wink – flakes Sep 2 '14 at 15:46
• @OMGtechy Thank you I will take a good look at it :) – Diba SH Sep 2 '14 at 15:51
• @Calpratt hmm... I'm not sure exactly what you mean :( – Diba SH Sep 2 '14 at 15:52
• You should read up on prime sieving methods. There are several questions on this site that solve exactly the same problem. – Nobody Sep 2 '14 at 15:53

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).

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.

• Oh my gosh thank you so much! I really appreciate it! THANK YOU THANK YOU THANK YOU – Diba SH Sep 2 '14 at 16:02