How to make the Sieve of Eratosthenes faster?

Question

I am trying to solve the 10 problem in the Project Euler. It consists on finding the sum of all the primes below two million. I wrote the following code based on the Sieve of Eratosthenes.

import time
t0 = time.time()
n=200000
liste=list(range(2,n))
k=2
s=2
while k <=n:
    liste=list(set(liste)-set(range(k,n,k)))
    if liste!=[]:
        k=min(liste)
        s+=k
    else:
        break
print(s)
t1 = time.time()
total = t1-t0
print(total)

I tested the above code for n=200000, but it is too slow for n=2000000. I would be very thankful to get any help to improve this program.

Answer 1

Always try to measure empirical complexity of your code at several ranges.

Your code is slow because of how you find the set difference, and that you always convert between set and list and back. You should be using one set throughout, and updating it in place with

    sete.difference_update(range(p*p,n,p*2))

To find the min element, you can just call min(sete) on the set, no list conversion required.

Because of the inefficient search for the min element the overall complexity of the resulting code will be nearing n^1.5, which is not too bright, but not too terrible either. In particular, it finishes in under 4.9 seconds on ideone.com, finding the sum for the primes below 2000000, and 0.5 seconds for 400000 (with the additional optimization of working with odds only, in the first place).

Answer 2

For finding the sum of prime numbers below 200000, the code below(using sieve of eratosthenes), works much faster, Your code takes nearly 55secs, whereas the code below takes just 0.8secs to execute!

import time
t0 = time.time()
n = 200000
sieve = [True] * (n + 1)
for i in range(2, n + 1) :
  if sieve[i] :
     for mult in range(i + i, n + 1, i) :
        sieve[mult] = False
s=0     
for i in range(2,n + 1):
    if sieve[i] :
        s+=i    
print(s)
t1 = time.time()
total = t1-t0
print(total)