<分区>
我对编程还很陌生,所以我决定做一些练习来提高我的能力。我被一个练习卡住了:“找出两百万以下所有素数的总和。”我的代码太慢了。
最初,我尝试将其作为一个普通的素数问题来解决,结果是这样的:
sum = 2 + 3
for i in range (5, 2000000, 2):
for j in range (3, i, 2):
if i%j == 0:
break
else:
sum += i
print(sum)
这样,所有的偶数都会被排除在循环之外。但这并没有解决我的问题。这里的量级真的很大。
所以我试图了解这段代码发生了什么。我在循环内有一个循环,循环内的循环运行外部循环时间的索引(不完全是因为列表不是从 0 开始的),对吧?因此,当我试图找到 20 以下的素数时,它运行外部循环 8 次,但内部循环运行 60 次(我不知道这个数学是否正确,正如我所说,我对编程非常了解)。但是当我将它与 2,000,000 一起使用时,我总共运行了大约 999,993,000,012 次内部循环,这太疯狂了。
我的 friend 告诉我埃拉托色尼筛法,我尝试创建一个新代码:
list = [2]
list.extend(range(3, 2000000, 2))
for i in list:
for j in list:
if j%i == 0 and j > i:
list.remove(j)
print(sum(list))
这就是我在尝试模拟筛子时取得的成果(忽略偶数有帮助)。它要快得多(使用其他代码,找到 200,000 以下的素数需要很长时间,而使用这个新代码我可以做到)但是在合理的时间内计算 2,000,000,000 是不够的。自从我开始编写代码以来,代码就在后台运行,但仍然没有。我不知道这个东西循环了多少次,我现在想都累得想不起来。
我是来求助的。为什么这么慢?我应该学习/阅读/做什么来改进我的代码?还有比这个筛子更有效的方法吗?感谢您的宝贵时间。