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

2022-05-12 00:00:00 python python-3.x primes primality-test

问题描述

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

相关文章