Python中如何判断一个数是否为质数？

判断一个数是否为质数是一个经典的数学问题，在Python中有多种算法可以实现。本文将介绍三种常见的算法：试除法、改进的试除法和 Miller-Rabin 算法。

1. 试除法

试除法是最简单直观的判断质数的方法。对于某个数 n，判断它是否为质数，只需要试除它所有比它小的数，如果除到某个数 x 后可以整除，那么 n 就不是质数。如下是用 Python 实现的代码：

def is_prime(n):

    if n < 2:

        return False

    for i in range(2, n):

        if n % i == 0:

            return False

    return True

需要注意的是，这种方法虽然直观易懂，但时间复杂度为 O(n)，所以对于大数判断质数时非常耗时。

2. 改进的试除法

上述的试除法过于暴力，我们可以改进一下算法。事实上，我们无需试除 n 所有比它小的数，我们只需要试除 n 的平方根即可，因为如果一个数非常大，比它大的数一定是它本身的倍数。

此外，我们还可以对 2 和 3 进行特判，避免不必要的运算。如下是改进后的代码：

def is_prime(n):

    if n < 2:

        return False

    if n == 2 or n == 3:

        return True

    if n % 2 == 0 or n % 3 == 0:

        return False

    for i in range(5, int(n ** 0.5) + 1, 6):

        if n % i == 0 or n % (i + 2) == 0:

            return False

    return True

时间复杂度为 O(√n)，效率比试除法高。

3. Miller-Rabin 算法

Miller-Rabin 算法是一种随机算法，通过多次检验来判断一个数是否为质数。算法具体流程如下：

（1）将 n - 1 写成 (2^s) * d 的形式，其中 s >= 1，d 为奇数；

（2）在 [2, n-2] 中找到一个随机整数 a；

（3）计算 a^d % n，如果余数为 1 或 n-1，则 n 是可能为质数，进入步骤（5）；

（4）重复步骤（3）s-1 次，每次将余数平方取模，如果某个余数为 n-1，则 n 是可能为质数，进入步骤（5）；

（5）重复步骤（2）至多 k 次，如果 n 是可能为质数，则返回 True，否则返回 False。

其中 k 为检验次数，k 越大算法越准确，但同时也越耗时。

下面是用 Python 实现的代码：

import random

def is_prime(n, k=10):

    if n <= 1:

        return False

    if n == 2 or n == 3:

        return True

    if n % 2 == 0:

        return False

    # 将 n - 1 写成 (2^s) * d 的形式

    d, s = n - 1, 0

    while d % 2 == 0:

        d //= 2

        s += 1

    for _ in range(k):

        a = random.randint(2, n - 2)

        x = pow(a, d, n)  # 计算 a^d % n

        if x == 1 or x == n - 1:

            continue

        for _ in range(s - 1):

            x = pow(x, 2, n)  # 计算 x^2 % n

            if x == n - 1:

                break

        else:

            return False

    return True

Miller-Rabin 算法时间复杂度为 O(k * log(n)^3)，其中 k 是检验次数。

综上所述，我们可以通过这三种算法来判断一个数是否为质数。对于小的数，试除法和改进的试除法效率较高，对于大数，Miller-Rabin 算法更为可靠。