python - 为什么我的素数检查代码没有显示正确的输出？

Question

我有一个代码可以检查一个数字是否为素数，并相应地输出"is"或“否”。但是当我输入 1763 时，即使它不是质数，它也会输出"is"。该代码通过检查一个数字是否可以被 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()

Answer 1

问题是您没有考虑所有除数。一旦第一个条件 (if n%i==0:) 为 false，就执行第二个 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