为什么我的质数校验码没有显示正确的输出？

Question

我有一个代码可以检查一个数是否为质数，并相应地输出 "Yes" 或 "No"。但是当我输入 1763 时，即使它不是质数，它也会输出 "Yes"。该代码通过检查一个数是否可以被 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:) 为假，您就执行第二个 elif 条件并打印 "Yes"。

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

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

Answer 2

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

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

for i in range (2,n):
    if n%i==0:
        print("No")
        return
print("Yes")

Answer 3

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

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")

为什么我的质数校验码没有显示正确的输出？

Why is my prime number checking code not displaying the correct output?

python

python-3.x

primes

primality-test