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?

• Cilyan: There is a lot you can do to improve performances in this script. The first for loop can be replaced with primes = list(range(2,2000000)), primes[len(primes)-1] is primes[-1] and the last for loop is sump = sum(primes). I don't think that's your problem, but it's a start.
• Wooble: Is this Python 2? Have you done any profiling before asking?
• Arunmu: Try moving the value of len(primes) into a variable and use that in the while loop. And try modifying the expression to "j*(j+k)" to "jj + j * k" where "jj" is pre calculated and put into some variable which would be used in computing the value of the expression
• Ricardo Cárdenes: Tight loops are not exactly Python strongest point. Removing the inner loop with an equivalent idiomatic construct would improve things a lot. Eg. primes = [x for x in primes if x % j or x == j]. Even creating a completely new list each loop, this is orders of magnitude faster
• Wooble: Anyway, yes, list.remove is an O(n) operation; first it needs to search through the list to find the item, then move all of the items after it in the list one spot to the left. Using a set would be much more efficient.

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)

• Metaliinuxite: Thanks, this is helpful (: This was actually a (failed) implementation of Sieves of Eratosthenes. I see that the list.remove method isn't the right thing to use, thanks!