1

This does the job in ~0.7s (2.2GHz i7 quad core), but I know it can be much faster. I think learning how to speed this up could teach me a lot about Python. How do I speed this up? How do I make it more memory efficient? (without using multiprocessing and still using the sieve of eratosthenes)

from math import sqrt
import time

def sum_range(n):
    A = [1 if i > 1 else 0 for i in xrange(n+1)]
    for i, p in enumerate(A):
        if A[i] and i <= int(sqrt(n)):
            for j in xrange(i+i, n+1, i):
                A[j] = 0
    sum = 0
    for i, p in enumerate(A):
        if A[i]:
            sum += i
    return sum

if __name__ == '__main__':
    t0 = time.time()
    sum = sum_range(1000*1000*2)
    t1 = time.time()
    print "The sum is {} and it took {} seconds to do this".format(sum, t1-t0)

For the record this isn't a homework problem of any kind. Simply just for curiosity.

the tao
  • 253
  • 2
  • 6
  • 13
  • 2
    Square roots are expensive, use i² < n instead. Also, maybe it's possible to take the sum of all numbers under 2 million and then subtract the ones that aren't primes? (That way, you'd only have one loop.) – m69's been on strike for years Apr 15 '17 at 00:16
  • 4
    This is [Project Euler problem #10](https://projecteuler.net/problem=10). Also, this question is more suitable for https://codereview.stackexchange.com/ – Nayuki Apr 15 '17 at 00:17
  • If numba is allowed I would try that first – Vince W. Apr 15 '17 at 00:18
  • 1
    Using `[0,0] + [1]*(n-1)` may be faster to declare your array – Nick is tired Apr 15 '17 at 01:01
  • Only use the sieve to get the primes up to the root and for the rest of the odd numbers check if they are dividable by any of the primes found with the sieve. This is much faster. – maraca Apr 15 '17 at 16:55

1 Answers1

0

There are only 223 primes below sqrt(2 * 10^6). How did I found out? Went to wolframalpha and entered "number of primes below sqrt(2e6)". Sorry this is Java, but it should also be applicable to Python.

long sum = 2; // treat 2 separately
int len = (int) Math.sqrt(2000000) + 1, count = 0;
boolean[] sieve = new boolean[len];
int[] primes = new int[222]; // without 2
// do sieve only with the odd numbers and up to the root
for (int i = 3; i < len; i += 2) {
    if (!sieve[i]) {
        sum += i;
        primes[count++] = i;
        for (int j = 3 * i; j < len; j += 2 * i) // again only odd numbers
            sieve[j] = true;
    }
}
outer:
for (int i = len % 2 == 0 ? len + 1 : len; i < 2000000; i += 2) {
    for (int j = 0; j < primes.length && primes[j] * primes[j] <= i; j++)
        if (i % primes[j] == 0)
            continue outer;
    sum += i;
}

For further improvement you can also skip all the numbers dividable by 3 (every third odd number will be dividable by 3).

maraca
  • 8,468
  • 3
  • 23
  • 45