Calculate the sum of all primes below two million - code takes too long

Question

The code does what is supposed to do for smaller values of n, but I would like to calculate the sum for all primes that are below two million, and that's where the code seems to take an endless amount of time. I am working with PyScripter. Is there any way to make this code more efficient?

def is_prime(a):
    return all(a % i for i in range(2, a))

def sum_of_primes(n):
    sum = 0
    x = 2
    while x < n:
        if is_prime(x):
            sum = sum + x
        x = x+1
return sum

def main():
    print(sum_of_primes(2000000))

if __name__ == '__main__':
    main()

You only need to check up to the square root of a for a start. Also consider holding an array of flags to mark off primes — Blue Granny, Oct 03 '17 at 14:15
you have an indentation problem in `x = x + 1`. Right now your code goes into infinity loop. — slallum, Oct 03 '17 at 14:17
Consider the `sieve of eratosthenes` algorithm for finding primes. — Samer Tufail, Oct 03 '17 at 14:27
see https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n?rq=1 — Fredrik Pihl, Oct 03 '17 at 14:27

score 3 · Accepted Answer · edited Oct 03 '17 at 15:29

Sieve of Eratosthenes is one of the best algorithm of finding all prime numbers below some number.

Basicly you create a list of booleans with the size of range 2 to whatever number you want. Then you remove all the indexes of each true values index folds. Such as after you start searching list you came across 2 and you update to false all the indexes of 2*n then you jump to 3 then you update all 3*n indexes to false. Then you skip 4 since you have already updated it to false. Then you came to 5 and replace all 5*n to false. End so on. At the and you will get a long list that all true valued indexes are prime number. You can use this list as you want.

A basic algorithm as pointed out by Wikipedia would be:

 Let A be an array of Boolean values, indexed by integers 2 to n, 
 initially all set to true.    

 for i = 2, 3, 4, ..., not exceeding √n: 
 if A[i] is true:
      for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
        A[j] := false.     
 Output: all i such that A[i] is true.

Calculate the sum of all primes below two million - code takes too long

1 Answers1