# Sum of primes program is taking too long

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?

• 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. Feb 10 '14 at 16:16
• Is this Python 2? Have you done any profiling before asking? Feb 10 '14 at 16:19
• 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 Feb 10 '14 at 16:20
• 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 Feb 10 '14 at 16:22
• 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. Feb 10 '14 at 16:28

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:

• 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! Feb 10 '14 at 16:43