Sum of primes program is taking too long

Question

I don't understand what is taking the program so long:

#!/bin/python

primes=[]
i=0
j=0
k=0

for i in range(2,2000000): #fill in the list
    primes.append(i)

i=0
while i<len(primes):
    j=primes[i]
    print(j)
    k=0
    while j*(j+k)<primes[len(primes)-1]: ##referred as 'line A'
        try:
            primes.remove(j*(j+k))
        except ValueError:
           k=k+1
           continue
        k=k+1
    i=i+1

sump=0
i=0
for i in range(len(primes)):
    sump=sump+primes[i]

print(sump)

I understand why the overall code is very inefficient, but line A takes 2 hours for j=2, and I don't understand why that is. Surely the list.remove(x) method is very inefficient?

Answer 1

I don't believe it is actually the specific Lne A that is the problem, but everything that is happening inside that loop, and most importantly, the line: primes.remove(...). From this StackOverflow answer you can see that remove(...) is an O(n) operation, thus it's performance is relative to the amount of data in the array. In this case, there's a lot.... and you are doing a lot of removes() since you are essentially removing all even values except 2.

What you should be doing is using a more efficient algorithm. You should read up on the Sieve of Eratosthenes, and introduce that algorithm here.

it will be much faster because it does not do any array-size changes. There are a number of posts here on CodeReview that have this problem solved quite nicely:

• Sieve of Eratosthenes: making it quicker
• Project Euler: primes in Python

(Primes in Python...)

(Sieve in other languages)