得到质数的错误答案

问题描述

我在此代码中得到了几个不正确的答案。例如，9显示为质数。我猜我的问题是使用中断，但我似乎无法从逻辑上找出有人问我的这个简单代码有什么问题。

for number in range(0, 1000):

    for x in range(2, number):
         if (number % x == 0):
             break
         else:
             print x
             break

---

解决方案

在您的脚本中，无论数字是否被2整除，它都会立即中断循环。 我已重新缩进代码，这可能更接近您要做的事情。

在原始代码中，如果数字可以被2整除(range(2,number)中的第一个数字)，那么您将中断循环，如果不可除，您也将中断循环。所以所有的奇数，比如9，看起来都像素数。

for循环运行后的else关键字仅当循环正常退出。因此，只有在没有找到除数的情况下，才会打印"is Prime"部分。

for number in range(0,1000):
    for x in range(2,number):
        if(number % x == 0):
            print number,"divisible by",x
            break
    else:
        print number, "is prime"

您可以在这里看到这是一个选项：http://codepad.org/XdS413LR

此外，这是一个简单的算法(不是对代码的批评，探索简单的算法是一项有用的研究)，但您可以使其更高效一些。从技术上讲，您只需要检查number的平方根，因为任何大于平方根的数字都必须有一个小于平方根的补数，而平方根应该已经遇到了。因此，代码中的逻辑可以更改为：

from math import sqrt
for number in range(0,1000):
    for x in range(2,int(sqrt(number/2))):
        # Rest of code as above.

这就是说，有很多方法可以优化质数的检查或发现，如果有机会，这些方法值得研究。