1

我有一个代码可以检查一个数字是否为素数，并相应地输出“是”或“否”。但是当我输入 1763 时，即使它不是素数，它也会输出“是”。该代码通过检查一个数字是否可以被 2 到 n-1 之间的任何数字整除来检查它是否是素数。所以当我输入 1763 时，它应该输出“No”，因为 1763 可以被 41 整除。我的代码出了什么问题？

def getNumber():
    n=int(input())
    return n

def isPrime(n):
    if n==2:
        print("Yes")
    else:
        for i in range (2,n):
            if n%i==0:
                print("No")
                break
            else:
                print("Yes")
                break

def main():
    n = getNumber()
    isPrime(n)

main()
4

3 回答 3

1

问题是您没有考虑所有除数。一旦您的第一个条件 ( if n%i==0:) 为假，您就执行第二个elif条件并打印“是”。

解决方案：您可以使用一个标志，该标志只有在找到除数时才会变为 1，这意味着该数不是素数。以下是您的代码稍作修改（仅显示部分代码，其余与您的相同）。正如@bereal 在评论中指出的那样，您不需要迭代到n但只需要迭代到 square root sqrt(n)。math.ceil返回最接近的四舍五入整数。

import math
def isPrime(n):
    flag = 0
    if n==2:
        print("Yes")
        return
    else:
        # for i in range (2, n):
        for i in range (2, math.ceil(np.sqrt(n)) + 1):
            if n%i==0:
                print("No")
                flag = 1
                break

    if not flag:
        print ("Yes")

1763
No
于 2018-10-15T10:40:17.040 回答
0

在您的循环中，您会在第一次迭代时中断，即使您还不能证明它不是素数。

只有在检查了所有可能的除数后才需要打印 yes n（实际上只检查所有数字到 的平方就足够了n）。

for i in range (2,n):
    if n%i==0:
        print("No")
        return
print("Yes")
于 2018-10-15T10:41:11.650 回答
0

只有在遍历所有可能的除数而没有找到一个除数之后，您才应该将一个数字声明为素数。为此，您可以改用该for-else构造，其中仅在未使用语句中止循环else时才执行该块：forbreak

def isPrime(n):
    if n==2:
        print("Yes")
    else:
        for i in range (2,n):
            if n%i==0:
                print("No")
                break
        else:
            print("Yes")
于 2018-10-15T10:41:13.133 回答