使用Python检查一个数字是否为质数

Question

可能的重复问题：
在Python中列出所有小于N的质数的最快方法
在Python中检查一个数字是否是质数

我正在做Project Euler的第10题，题目是这样的：

Find the sum of all the primes below two million.

这是我的程序：

numbers = []
sum = 0
range_number = 2000000

#Appends all numbers in range
for i in range(2, range_number):
    numbers.append(i)

#i is every entry in numbers, n is the multiples of numbers[i] starting at one 
#value of numbers[i] after i. This is the Sieve of Eratosthenes.
for i in range(0, len(numbers)-1):
    if numbers[i] != None:
        for n in range(i + numbers[i], len(numbers)-1, numbers[i]):
            numbers[n] = None

#Adds all the numbers that are not None
for i in numbers:
    if i != None:
        sum += i

print(sum)

我的程序把范围内每个数字的倍数都变成了None，这样应该能去掉所有合数，只留下质数。

当我输入一个简单的范围数字，比如10时，我得到了错误的答案。请不要只发你自己的程序，告诉我我哪里出错了。其他帖子提到要用平方根，但我没太明白。

谢谢。

Answer 1

你的问题是，你从来没有把数字列表中的最后一个数字去掉。如果范围数字是21，那么数字列表的长度是20，而长度减去1就是19。所以这行代码：

for n in range(i + numbers[i], len(numbers)-1, numbers[i]):

实际上并没有把数字20从列表中移除。如果你打印出这个列表就能看到这一点。目前你的解决方案在范围数字比一个质数大1时是正确的，但在范围数字比一个合数大1时就会少算一个。

要解决这个问题，只需把那行代码改成：

for n in range(i + numbers[i], len(numbers), numbers[i]):