5
\$\begingroup\$

(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)
\$\endgroup\$
  • \$\begingroup\$ Take a look at this \$\endgroup\$ – OMGtechy Sep 2 '14 at 15:28
  • \$\begingroup\$ 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 \$\endgroup\$ – flakes Sep 2 '14 at 15:46
  • \$\begingroup\$ @OMGtechy Thank you I will take a good look at it :) \$\endgroup\$ – Diba SH Sep 2 '14 at 15:51
  • \$\begingroup\$ @Calpratt hmm... I'm not sure exactly what you mean :( \$\endgroup\$ – Diba SH Sep 2 '14 at 15:52
  • \$\begingroup\$ You should read up on prime sieving methods. There are several questions on this site that solve exactly the same problem. \$\endgroup\$ – Nobody Sep 2 '14 at 15:53
8
\$\begingroup\$

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.

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

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.