为什么质数检查器说 9 是质数？

Question

print "Type a number"
num = int(raw_input("> "))

if num % 2 == 0:
    print "This is not a prime number"

else:
    print "This is a prime number"

当我输入“9”时，它说这是一个素数，但事实并非如此：

Type a number
> 9
This is a prime number

我的代码是不是太简单了？有没有它不检查的东西？

Answer 1

您只是通过检查它是否可以被 2 整除来检查它是否为偶数。但是 9 可以被 3 整除，因此您还需要检查它。最简单的方法是检查所有数字直到您要检查素数的数字的平方根。

Answer 2

你在这里所做的只是检查一个数字是否可以被 2 整除。因为 9 / 2 = 4.5，它不能被 2 整除，因此转到 else 子句。

这是您可能想要的精简版本：

def is_prime(a):
    return all(a % i for i in xrange(2, a))

Answer 3

您正在检查给定数字是否为偶数，而 9 不是偶数，因此您的代码打印出来 "This is a prime number"

请查看 this Whosebug 问题，详细了解如何使用 Python 检查素数。

Answer 4

要检查数字是否为质数，您必须验证它是否可以被 [2, sqrt(n)] 范围内的任何数字所识别。

以下代码的作用完全相同：

import math

def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

这种方法适用于小数，但如果 n 是真正的大数，那么您需要更快的方法。在这种情况下，您可以使用 Miller–Rabin primality 测试以一定的概率检查素数。

Why does prime number checker say 9 is a prime number?