想知道为什么is_素数函数的结果不正确吗

Question

def is_prime(x):
    for i in range(2,x):
        if (x % i) == 0:
            return False
        else:
            return True

print(is_prime(9))

这是我寻找素数的函数，我不知道为什么9总是返回True，有什么帮助和解释吗？谢谢

Answer 1

要理解为什么会发生这种情况，请看一下9被传递到is_prime时会发生什么：

我们输入for循环，并将i的初始值设置为2。然后，9 % 2 = 1，而不是0，因此if条件失败，我们转到else条件，然后立即返回True：但这不是素性的定义。我们需要9不能被任何小于它的数整除（除了1），而不是不能被单个数整除。因此，我们只能在选中范围内的所有数字后返回True，如下所示：

def is_prime(x):
    for i in range(2,x):
        if (x % i) == 0:
            return False
    return True

您的代码现在应该返回9的正确结果（并且，给定无限时间，任何大于1的自然数）

需要考虑的几件事：是否需要检查range(2, x)中的每个数字？也许你可以看看x的平方根之后发生了什么？此外，您可能需要检查数字是否小于2（即：1，0，-1，…），因为当前代码不会给出这些数字的正确结果。如果你也感兴趣的话，Sieve of Eratosthenes是一种比试除法更好的寻找素数的算法，你可能想进一步了解一下