为什么第一个解决方案比第二个慢得多，计算素数的总和？

Question

我正在解决欧拉的项目问题（在 python 中），我必须计算所有小于 200 万的素数的总和，我想出了两个解决方案，但只有一个得到了结果，因为另一个太慢了。这是我第一个太慢的解决方案：

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)

这是我的第二个解决方案，计算总和的速度相当快：

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)

我想知道的是，为什么最后一个几乎是瞬间计算出总和，而另一个在几分钟后甚至没有得出结果？

Answer 1

查看代码中的循环数。在第一个解决方案中，您有大约 4 个循环 for x in list、for d in range(x,n,x):、(d in list) 和 list.remove(d) 也循环遍历列表以删除 d。但是对于第二种解决方案，你只有两个循环 for x in list : 和 for d in range(x,n,x):

为什么第一个解决方案比第二个慢得多，计算素数的总和？

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

python

performance

primes