如何判断一个数是质数

质数又称为素数，是指除了1和自身外，不能被其他正整数整除的自然数。判断一个数是否为质数是数学中的基本问题之一，也是密码学等应用领域的基础。

一、试除法判断质数

试除法是判断一个数是否为质数的最简单方法，也是最常用的方法之一。它的思路是从2到n-1逐个测试n能否被整除，如果n能被2到n-1中任意一个数整除，那么n就不是质数，否则即为质数。

示例代码如下：

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

以上代码先判断n是否小于2，因为小于2的数都不是质数。然后从2到n-1逐个测试n是否能被整除，如果能被整除，直接返回False；否则返回True。

这种方法的时间复杂度是O(n)，当n非常大时，其判断效率会非常低下。为了提高效率，可以考虑一些优化方法。

二、试除法优化

1. 循环优化

循环优化是最基本的优化方法，可以减少循环次数，提高效率。在试除法中，循环范围可以从2到$\sqrt{n}$，因为如果n有一个因子大于$\sqrt{n}$，那么一定有一个因子小于$\sqrt{n}$，因此只需要测试2到$\sqrt{n}$的因子即可。

示例代码如下：

import math

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

以上代码中，使用math库中的sqrt函数计算n的平方根，并转换为整数，从而减少循环次数。

2. 除2优化

除2优化指的是，在试除法中，先特判2这个质数，然后只测试奇数。

示例代码如下：

import math

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

以上代码中，首先特判2这个质数，然后判断n是否为偶数，如果是，直接返回False。然后从3开始，每次增加2，只测试奇数。

3. 质数表优化

质数表优化是一种预处理优化方法，即先生成2到n之间的所有质数，然后判断n是否在质数表中。

示例代码如下：

import math

def generate_primes(n):
    primes = []
    is_prime = [True] * (n+1)
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i**2, n+1, i):
                is_prime[j] = False
    return primes

def is_prime(n):
    if n < 2:
        return False
    primes = generate_primes(n)
    return n in primes

以上代码中，generate_primes函数用于生成2到n之间的所有质数，is_prime数组用于标记是否为质数，初始值为True。然后从2开始，对于每个质数i，将i的倍数标记为False，最后返回primes数组。is_prime函数首先判断n是否小于2，然后调用generate_primes函数生成质数表，最后判断n是否在质数表中。

三、米勒-拉宾素性检验

米勒-拉宾素性检验是一种更加高效的判断质数的方法，它可以在多项式时间内判断n是否为质数。其基本思想是利用费马小定理和随机数生成器，随机选取几个数测试n是否为合数。

该算法的核心是对费马小定理的应用，即：

若p为质数，a为任意正整数，则a^{p-1} \equiv 1 \ (\mathrm{mod}\ p)。

示例代码如下：

import random

def is_prime(n, k=5):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    d = n-1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for i in range(k):
        a = random.randint(2, n-2)
        x = pow(a, d, n)
        if x == 1 or x == n-1:
            continue
        for j in range(r-1):
            x = pow(x, 2, n)
            if x == n-1:
                break
        else:
            return False
    return True

以上代码中，k为测试次数，d和r用于分解n-1，a为随机选取的数，x为中间变量。首先特判n是否为2或3，然后判断n是否为偶数。

随后将n-1分解成2^r*d的形式，然后从2到n-2随机选取a。根据费马小定理，a^d mod n等于1或n-1时，n有可能是质数，继续选取下一个随机数。否则根据二次探测定理，对于任意的正整数x，x^2 ≡　x^2 mod n，因此如果a^d mod n不等于1或n-1，则继续计算x = a^(2d) mod n，直到找到一个x使得x^2 ≡ 1 mod n，则n可能是合数。这个过程可以用循环和break语句实现，时间复杂度为O(klog^3n)。

通过多次测试，如果每次都返回True，那么n有极大的概率是质数。根据严谨证明，当测试次数k足够大时，错误率可以降到非常低。

总结

本文介绍了判断质数的常见方法：试除法和米勒-拉宾素性检验。试除法是简单有效的算法，但随着数的增大，算法效率下降，因此需要考虑一些优化方法。米勒-拉宾素性检验是一种高效的算法，可以在多项式时间内判断质数，但需要使用随机数生成器来测试。在具体应用中，可以根据实际情况选择合适的算法。