如何判断一个数是否是质数？

质数又称素数，指的是大于1且只能被1和自身整除的整数。判断一个数是否为质数，是数论与日常编程中最基础的问题之一。根据数的范围不同，我们可以选择从简单试除到概率算法的多种方案。

最基础的试除法

最直观的思路是从2开始，依次用每个小于n的整数去除n，如果其中存在某个数能整除n，那么n就不是质数。这种方法逻辑简单，适合刚接触算法的初学者理解质数的数学定义。

不过这种写法效率很低。假设我们要判断n是否为质数，最坏情况下需要循环n减2次。当n很大时，这种线性增长的时间复杂度完全不可接受。下面的代码展示了最原始的写法：

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

# 测试
print(is_prime_basic(17))  # True
print(is_prime_basic(15))  # False

上述代码在n为100万时，需要执行接近百万次取模运算，显然不适合处理稍大的数值。但它的价值在于清晰地表达了质数“无其他因素”的定义。

优化到平方根的试除

数学上有一个重要性质：如果n可以分解为a乘b，且a小于等于b，那么a最大不会超过根号n。这意味着我们只需检查2到根号n之间的整数，就能覆盖所有可能的因数组合。

将循环上限改为整数平方根后，时间复杂度从O(n)降为O(根号n)，性能提升非常明显。对于绝大多数工程场景下的中等大小整数，这种写法已经足够快，而且结果是绝对准确的。

import math

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

# 测试
print(is_prime_sqrt(97))   # True
print(is_prime_sqrt(100))  # False

代码中还顺手排除了偶数，进一步将循环次数减半。这种小优化在批量判断时积累起来的收益很可观。

跳过更多倍数的进阶试除

除了排除偶数，我们还可以利用“质数大于3时都满足6k加减1”的规律。任何整数都可以写成6k、6k加1、6k加2、6k加3、6k加4、6k加5，其中能被2或3整除的形式都不是质数（除2和3本身）。

因此判断时只需测试6k减1和6k加1形式的数，能把候选除数再缩减约三分之一。虽然复杂度阶数没变，但常数因子更小，实际运行更快。

import math

def is_prime_6k(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# 测试
print(is_prime_6k(101))  # True
print(is_prime_6k(91))   # False，7乘13

这种写法在单线程Python里判断千万级别以内的数都很轻松，是手写工具函数时的常用选择。

大数场景下的米勒拉宾测试

当数字达到几十位甚至上百位的加密场景时，试除法彻底失效。此时通常采用米勒拉宾这种概率性素数测试：它基于费马小定理的变体，通过随机选取底数进行幂模运算，能在极短时间内以极高概率给出正确结论。

米勒拉宾测试本身可能把极少数“强伪素数”误判为质数，但多轮不同底数测试后错误率可降到忽略不计。下面是Python中使用标准库实现的示例：

import random

def is_prime_miller_rabin(n, k=5):
    if n < 2:
        return False
    # 小数字直接试除
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
        if n % p == 0:
            return n == p
    # 写出 n-1 = d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# 测试
print(is_prime_miller_rabin(999983))  # True

该算法时间复杂度为O(k乘log三次方n)，适合密码学、随机大质数生成等任务。如果业务要求绝对确定性，可结合确定性的米勒拉宾底数集合使用。

不同方案的选用建议

对于日常接口开发或面试题里常见的三十二位以内整数，平方根试除或6k优化法已经完全够用，代码易读且零依赖。若你处理的是批量小数据，还可以预先筛出质数表再用查表法加速。

一旦涉及安全通信、密钥生成等超大整数，请直接使用语言标准库或成熟加密库中的概率测试，不要自己造轮子试除。下表简要对比了几种方法：

理解这些方法的底层差异，你就能在写代码时针对数据规模做出合理的取舍，而不是盲目套用某一种写法。

质数判断素数算法时间复杂度修改时间：2026-08-01 03:39:31