python - is_prime 函数在测试 121 时失败，不知道为什么

Question

我正在尝试编写一个接受整数 x 的函数，如果是素数则返回 True，否则返回 False。它工作正常，除了测试数字 121 时，我不明白为什么。这是我的代码:

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

当检查 121 时，它似乎跳过了 if x%i == 0:，因为 121%11 是 0，但它不会返回 False .我在这里遗漏了一些明显的东西吗？感谢我能得到的任何帮助，谢谢。哦，我正在使用 Python 2.7

Answer 1

你几乎拥有它。你只需要一个小小的改变

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

您面临的问题是由于您不允许循环在返回之前完成对所有数字的检查

考虑在 121 上运行代码时的前几次迭代:

函数说:

• x 是否小于 2？
• • 没有。继续
• x 正好是 2 吗？
• • 没有。继续
• 对于从 2 到 x-1 的所有数字(for i in range(2,x))
• • 现在 i 是 2
• • 121%2 正好是 0 吗？
• • • 没有。继续
• • else(好吧，121%2 不是 0，所以我进入这里)
• • • 返回 True <-- 糟糕!

所以您需要做的是，在决定返回之前完成遍历 for 循环中的所有这些数字，这就是我的修复程序所做的。

当然(正如 Joran Beasley 指出的那样)，您可以利用任何数字的除数都不大于其平方根的知识。所以你只需要检查数字本身的平方根:

def is_prime(x):
    if x<2:
        return False
    if x == 2:
        return True
    else:
        for i in xrange(2, int(sqrt(x))+1):
            if not n%i:
                return False
        return True