我想用Python找出200万以下所有素数的和

Question

ls = []
total = 0

for i in range(0,2000000):
    ls.append(i)

for i in range(2,2000000):
    for x in range(2,int(float(2000000/i)+0.5)):
        ls[int(float(i*x))] = 0
ls[1] = 0

for j in range(0,2000000):
    total += ls[j]
print total

这段代码给我的结果是错的。它包含了一些不是质数的大数字。而且它的数字比实际的质数多出了25个。

Answer 1

问题出在这一行代码上：

    for x in range(2,int(float(2000000/i)+0.5)):

在这个上下文中，float(2000000/i)并没有太大作用，你是不是想写成float(2000000)/i？因为你还是在做整数除法，然后再把结果转换成浮点数。所以，当i是947时，这样的计算结果是2111.0，而不是2111.93。这样一来，加上0.5后再用int()转换，实际上什么也没改变，结果还是2111。

这样就导致循环一直运行到2110，所以你没有标记到947 * 2111，这样就会出现错误的结果。

你可以稍微调整一下循环来解决这个问题：

for i in range(2,2000000):
    for x in range(2 * i, 2000000, i):
        ls[x] = 0

这样一来，你就不是先除再乘，而是直接遍历并标记所有i的倍数，直到2000000。

当然，还有其他（更好的）方法来解决这个问题，但我只是想指出如何改进你当前的解决方案。

Answer 2

你的算法结果不对，我看不太懂你用的是什么方法。如果能提供更多细节就好了。

有一种叫做埃拉托斯特尼筛法的算法，可以有效地生成质数。你可以在这个讨论串里找到对这个算法的详细解释，以及如何编写这个算法的内容。

import math
def primeNumbers(n):
    A = range(2, n + 1) 
    B, C= [],A
    while C[0]< math.sqrt(n): 
        firstElement= C[0]
        B+= [firstElement]
        C= [x for x in C if x%firstElement!=0] 
    return B+C 

t= sum(primeNumbers(2000000)) #you summ the prime numbers numbers 
print t