为什么我的质数检查代码不能显示正确的输出？

问题描述

我有一个代码，它检查一个数字是否为质数，并相应地输出"是"或"否"。但当我输入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()

---

解决方案

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

解决方案：您可以使用仅当找到除数时才变为1的标志，这意味着该数字不是质数。以下是您的代码稍作修改(仅显示部分代码，其余代码与您的代码相同)。正如@Bereal在注释中指出的那样，您不需要向上迭代到n，只需要向上迭代到平方根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