python之欧拉计划#10_编程设计

我对算法还很陌生，几周前才开始编码。请帮我解决这个问题:

10 以下的质数之和为 2 + 3 + 5 + 7 = 17。

求出 200 万以下的所有质数之和。

我尝试了通常的粗暴方法，当然很烂。我尝试阅读有关 Sieve Algorithms 的内容。并实现了这一点，是的，它只对奇数运行:

i=[x for x in range(3,2000001,2)] 
print(len(i)) 
j=0 
sum=2 
while(max(i)!=j): 
    m=0 
    while(m<(2000000-(i[j]**2)/(2*i[j]))): 
        a=(i[j]**2)+2*m*i[j]  
        if a in i: 
            i.remove(a) 
        m+=1 
    j+=1 
for s in range(1,len(i)+1): 
    sum+=i[s] 
print(sum)

程序仍然需要 5 个多小时。我在 3 小时内停止了它。我哪里错了？

请您参考如下方法:

看来你正在努力学习，所以我不会给你完整的解决方案，只是路径。

不要搞乱列表、将元素放入和取出、检查它们是否在里面等等。这是导致效率低下的原因。相反，保留一个已知素数列表。
写评论。我盯着你的代码看了几分钟，但我不知道它做了什么。
在适当的时候使用math 函数。 math.sqrt 比 **0.5 快(大约多 30%)。
这个 block : 对于范围内的 s(1,len(i)+1): 总和+=i[s] 疼。您只需输入 sum(i)
[x for x in range(3,2000001,2)] 与 range(3,2000001,2)(在 Python2 中)或 list(range(3,2000001,2))(在 Python3 中)。
不要将变量名用作i、a、m。目前尚不清楚它们是什么。

你怎么知道一个数是不是素数？对于它下面的所有素数，检查它们是否能整除你的数字。如果没有，请保存它。事实上，您只能检查那些小于您的数字的平方根的素数。

如果您想用内存换取速度，您可以使用@vamosrafa 的函数，然后执行sum(prime(2e6))。 (在 Python2 中，将 range 更改为 xrange)。您只需要内存来同时保存几个数字，但会做很多不必要的除法(如果它不能被 3 或 5 整除，它就不能被 15 整除)。