这两种质数检查算法有什么不同？

Question

所以最近我一直在尝试找出一个算法，用来检查这个数是否为质数。所以我想出了一个主意，让代码看起来像这样：

def if_prime(num):
   
    for divisor in range(2,num):
        if (num % divisor) == 0:
            return f"{num} is not prime"
        else:
            return f"{num} is prime"
print(if_prime(9))

所以基本上这段代码返回了错误的值，它说9是一个质数，显然不是，但是下面的代码似乎是有效的，我不知道有什么不同。

def if_prime(num):
    for divisor in range(2,num):
        if (num % divisor) == 0:
            return f"{num} is not prime"                                      
    return f"{num} is prime"

print(if_prime(9))

Answer 1

有很大的不同！

第一个错误！：

def if_prime(num):
   
    for divisor in range(2,num):
        if (num % divisor) == 0:
            return f"{num} is not prime"
        else:
            return f"{num} is prime"

这将检查一个数字是否有介于0和num之间的任何因子，如果找到一个因子，则返回该数字不是质数。

但错误是，如果它没有找到一个因子，那么它会立即返回true，并且不检查其他除数：

例如，这将说明9是一个质数，它不能被2整除，并且if条件变为false！

另一方面，第二个是正确的！

def if_prime(num):
    for divisor in range(2,num):
        if (num % divisor) == 0:
            return f"{num} is not prime"                                      
    return f"{num} is prime"

在这个例子中，我们也遍历了从2到num的所有除数，但是在这个例子中，如果有一个数不是除数(我们检查了所有可能的除数)，那么我们不会返回任何东西。因此，如果循环结束，没有找到除数，那么它就是质数！

但是这也有一个小bug，因为它会说1是一个质数！

下面是if_prime函数的一个适当而有效的版本：

def if_prime(num):
    for divisor in range(2, num/2):
        if (num % divisor) == 0:
            return f"{num} is not prime"                                      
    if num == 1:
        return f"{num} is not prime"
    else:
        return f"{num} is prime"

Answer 2

在您的第一个示例中，

else:
    return f"{num} is prime"

在第一次迭代后中断for循环，因为return会停止循环并返回方法的值

在您的第二个示例中，

return f"{num} is prime"

仅当for循环运行完成且未找到要返回的非质数值时才执行

Answer 3

你的第一个函数的问题是，如果num不能被2整除，它会返回一个假阳性，如果num不能被2整除，你需要继续前进。这在你的第二个函数中得到了纠正。

def if_prime(num):
    for divisor in range(2, num):
        if (num % divisor) == 0:
            return f"{num} is not prime"
    return f"{num} is prime"

在这里，执行else语句的唯一方式是if语句不返回任何内容。这仅仅意味着你没有找到从2到num的除数。所以这一定意味着num是质数。因此，它返回num作为质数。