How can I make Python work faster?

Question

I am trying to calculate the sum of all the prime numbers below 2 million and since I had already written a function to find the prime numbers which are less than a given number, I simply wrote a new one that calls the older function and sum the items in that list.

But it seems like it's taking forever. How can I speed this code up?

def find_primes(n):
    "Find the prime numbers below n"
    primes=[];
    for i in range(2,n):
        for fac in range (2,i):
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

def add_primes(m):
    "Sum all the prime numbers below m"
    newlist=find_primes(m);
    t=sum(newlist);
    return t

PS: I'm kind of a novice about Python, so I will be glad if you can nicely explain my mistakes. Thanks in advance.

By the way, the condition `i != fac` is *always* true since `range` does not yield the "stop" argument, and thus every loop is doing a useless comparison(even though it ought to be quite fast). — Bakuriu, Mar 24 '13 at 14:06

score 3 · Answer 1 · answered Mar 24 '13 at 13:59

3

Implement the Sieve of Eratosthenes. That'll make your code do a lot less work than it's doing currently, making it a lot faster.

answered Mar 24 '13 at 13:59

NPE

486,780
108
951
1,012

Thanks a lot, I couldn't think of using that one in my code. I'll try it immediately. – Dilan Toplu Mar 24 '13 at 14:04

score 0 · Answer 2 · answered Mar 24 '13 at 14:08

You can improve your current code by replacing the for fac in range (2,i) line with this:

for fac in primes:

code:

def find_primes1(n):
    "Find the prime numbers below n"
    primes=[2,3]     #initialize primes with 2 values
    for i in range(4,n):
        for fac in primes:
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

Timing comparisons:

In [6]: %timeit find_primes(10**4)   # your version
1 loops, best of 3: 2.33 s per loop

In [7]: %timeit find_primes1(10**4)
1 loops, best of 3: 171 ms per loop

In [8]: find_primes1(10**3)==find_primes(10**3)
Out[8]: True

But for larger values you should definitely learn the Sieve of Eratosthenes method.

How can I make Python work faster?

2 Answers2