得到质数的错误答案 [英] Getting wrong answers for prime numbers

查看:72
本文介绍了得到质数的错误答案的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我在此代码中得到了几个不正确的答案。例如,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.

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

这篇关于得到质数的错误答案的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆