CODEWITHSUNDEEP
pythonperformanceprimes
Pedro
Pedro

Reputation: 75

Why is the first solution way much slower than the second one, to calculate the sum of prime numbers?

I was solving a Euler's project problem (in python) where I had to calculate the sum of all prime numbers below 2 million, I came up with two solution but only one got me the result because the other one was too slow. This is my first solution that was too slow: 

n=2000000
list = list(range(2,n,1))

for x in list :
    if(x*x>n):
        break

    for d in range(x,n,x):
        if((x!=d) and (d in list) ):
            list.remove(d)
            continue


result=sum(list)        
print(result)

This is my second solution, which was pretty fast at calculating the sum:

n=2000000
list = list(range(2,n,1))
temp=list
for x in list :
    if(x*x>n):
        break
    if(temp[x-2]==0):
        continue
    for d in range(x,n,x):
        if(x!=d):
            temp[d-2]=0

result=sum(list)        
print(result)

What I would like to know is why the last one calculated the sum almost instantaneously while the other didn't even produce a result after several minutes?

Upvotes: 1

Views: 88

Answers (1)

RICKY KUMAR
RICKY KUMAR

Reputation: 673

Look for the number of loops in your code. In the first solution, you have around 4 loops for x in list, for d in range(x,n,x):, (d in list) and list.remove(d) also loop through the list to remove d. But in case of the second solution, you have only two loop for x in list : and for d in range(x,n,x):

Upvotes: 1

Related Questions