这两种素数检查算法有什么区别

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

所以基本上这段代码 returns 是错误的值，它说 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 之间的任何因数，如果它找到一个因数，它会 return 表示该数不是质数。

但错误在于，如果它没有找到一个因数，那么它 return 立即为真并且不检查其他除数：

例如，如果 9 不能被 2 整除并且 if 条件变为假，这会说 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"

在这一个中，我们也循环遍历从 2 到 num 的所有除数，但在这种情况下，如果一个数字不是除数，我们不会 return 任何东西（我们检查所有可能的除数）因此如果循环结束，我们发现没有除数那么这意味着它是一个质数！

但这也有一个小错误，因为它会说 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 方法中的值

在你的第二个例子中，

return f"{num} is prime"

只执行一次for循环运行完成没有找到非素数到return

Answer 3

你的第一个函数的问题是，如果 num 不能被 2 整除，它 return 是一个误报。如果 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 语句不会 return 任何东西时。它只是意味着你没有找到从 2 到 num 的约数。所以它必须意味着 num 是质数。因此它 returns num as prime.

这两种素数检查算法有什么区别

Whats the difference between those two prime number checking algorithms

python

primes