博客

下面是Python实现判断是否为素数的完整攻略。

什么是素数

在数学中，素数（prime number），又称质数，是指在大于 1 的自然数中，除了 1 和它本身以外，无法被其他自然数整除的数。

例如，2、3、5、7、11、13、17、19 等就是素数，而 4、6、8、9、10 等就不是。

判断素数的方法

判断一个数 n 是否为素数，最简单的方法就是对 2 到 $\sqrt{n}$ 中的每一个数进行判断，看是否能够整除 n。判断是否能够整除的方法就是用 n 对这个数进行取模运算，如果余数为 0，则表示能够整除，即 n 不是素数。

使用上述方法的一个优化是，在 2 到 $\sqrt{n}$ 中除以 2 以外的偶数可以直接跳过。因为如果一个数可以被偶数整除，那么这个数必定是偶数，而大于 2 的偶数都不可能是素数。

Python 实现

在 Python 中，我们可以使用如下的代码来判断一个数是否为素数。

import math

def is_prime(n):
    """
    判断一个数是否为素数

    Parameters:
    -----------
    n: int
        待判断的数

    Returns:
    --------
    bool
        如果 n 是素数，返回 True；否则返回 False.
    """
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False

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

    return True

这个函数首先判断 n 是否小于等于 1 或者是否为偶数，是的话直接返回 False。然后计算 $\sqrt{n}$，并从 3 开始，每次增加 2，循环到 $\sqrt{n}$ 中的所有奇数，对 n 逐一进行取模运算，如果能够整除，则返回 False，表示 n 不是素数。如果循环结束后仍然没有返回，则表示 n 是素数。

我们可以输入以下测试代码来验证上述实现：

print(is_prime(7))  # True
print(is_prime(24))  # False

其中第一个测试应该输出 True，第二个应该输出 False。

另外一种更加简洁但仍然相当高效的方法是使用 Python 中的 all 函数，例如：

import math

def is_prime(n):
    """
    判断一个数是否为素数

    Parameters:
    -----------
    n: int
        待判断的数

    Returns:
    --------
    bool
        如果 n 是素数，返回 True；否则返回 False.
    """
    if n <= 1:
        return False

    return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

其中 all 函数可以判断一个可迭代对象中的所有元素是否都为 True，如果都为 True，则返回 True，否则返回 False。因此上述代码可以先判断 n 是否小于等于 1，然后使用 all 函数判断 2 到 $\sqrt{n}$ 中的所有数是否都不能整除 n，如果都不能整除，则返回 True，表示 n 是素数。