程序员面试题精解（5）— 素数判定

发表于 2025-04-19 更新于 2025-05-02 分类于面试指南阅读次数：本文字数： 12k 阅读时长 ≈ 11 分钟

素数（Prime Numbers，又称质数）在密码学和加密通信中扮演着核心的角色，是现代网络安全技术的基石。同时，素数也广泛应用于高级编译器系统的“底层优化”、“散列设计”或“伪随机生成”模块中。如果要申请相关的软件工程师职位，一定要掌握素数搜寻与验证的编程诀窍。

The primes are the raw material out of which we have to build arithmetic.
— Carl Friedrich Gauss（卡尔·弗里德里希·高斯，德国数学家、物理学家、天文学家、大地测量学家。被普遍认为是有史以来最伟大的数学家之一，并享有“首席数学家”和“数学王子”美誉。）

素数搜寻

试除法

素数是除了自身和 1 以外，没有其它素数因子的自然数。根据此定义，最直观的判定正整数 \(n\) 是否是素数的方法，就是从 2 到 \(n-1\) 逐个试除。由此，要找到不大于给定数num的全部素数，解法是对 [2, num] 区间每一个数执行试除法。下面的 Python 函数就是这种朴素试除法的实现。

# Method 1: The search range is from 2 to (num-1) per definition.
# This is the slowest.
def get_prime_naive(n):
    prime_list = []
    for i in range(2, n + 1):
        flag = True
        for j in range(2, i - 1):
            if i % j == 0:
                flag = False
                break
        if flag:
            prime_list.append(i)
    return prime_list

不幸的是，朴素试除法也是最慢的解法，通过对范围内每个整数进行试除法来找出全部素数，其时间复杂度为 \(O(n^2)\)。有没有快一点办法呢？当然。我们知道最小的素数是 2，它也是最小的素因子，所以一个整数 \(n\) 最大的素因子一定不会大于 \(\lfloor\frac{n}{2}\rfloor\)。那么上面程序的内循环次数减半就可以了，修改后的程序如下

# Method 2: Cut the search range in half， to [2, floor(n/2)].
def get_prime_halfway(n):
    prime_list = []
    for i in range(2, n + 1):
        flag = True
        for j in range(2, i // 2 + 1):
            if i % j == 0:
                flag = False
                break
        if flag:
            prime_list.append(i)
    return prime_list

这种折半试除法确实可以加倍运行速度，但遗憾的是，其时间复杂度仍然为 \(O(n^2)\)。还能改进一下吗？

实际上，若 \({\displaystyle n=ab}\) 是个合数（其中 \({\displaystyle a}\) 与 \({\displaystyle b\neq 1}\)），则其中一个因数 \({\displaystyle a}\) 或 \({\displaystyle b}\)必定不大于\({\displaystyle {\sqrt {n}}}\)。即一个合数必须有一个因数小于或等于该数的平方根，否则该数就是素数。比如对于数 \(48\)，\(\sqrt{48}=6.9282\)，它的八个因数正好均匀分配在其平方根的两边 \[48=2\times24=3\times16=4\times12=6\times8\] 基于这个事实，我们可以进一步将试除的上限缩减到\(\lfloor{\displaystyle {\sqrt {n}}}\rfloor\)，就得到了常规试除法实现：

# Method 3: The search range is from 2 to floor(sqrt{N}).
# This is based on the fact that a composite number must have a
# factor less than or equal to the square root of that number.
# Otherwise, the number is prime.
def get_prime_regular(n):
    prime_list = []
    for i in range(2, n + 1):
        flag = True
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                flag = False
                break
        if flag:
            prime_list.append(i)
    return prime_list

可以看到，常规试除法将时间复杂度缩减到了 \(O(n\sqrt{n})\)，真的不错。

埃氏筛

“欲穷千里目，更上一层楼”。对于寻找不大于特定数的素数，还有更好的算法吗？确实有！那就是埃拉托斯特尼筛法（Sieve of Eratosthenes）。此算法得名于古希腊数学家埃拉托斯特尼¹。他独辟蹊径，从另一个角度探索问题的答案：与其对每一个数执行试除法，不如从最小的素数开始标记它所有倍数为合数，而下一个尚未被标记的最小自然数即是下一个素数。重复这一过程，就可以像筛子一样过滤掉给定范围内全部合数，剩下就都是素数了。

在实际的运用中，此算法后来又加入了两点改进：

标记某一素数 \({p}\) 的倍数时，可直接从 \(p^{2}\) 开始标记。因为所有小于 \(p^{2}\) 的 \({p}\) 的倍数必然有一个更小的素数为其因数，故它们之前已经被标记过了。
寻找 \({\displaystyle n}\) 以内的素数时，若找到了一个大于 \({\sqrt {n}}\) 的素数，则剩余的所有尚未标记的数也都是素数，算法可以提前结束。因为若这些尚未标记的数中有任意一个为合数，其两个因数必然都大于\({\sqrt {n}}\)，这是不可能的。

以18为例，若要找出不大于18的所有素数，使用上述改进过的埃拉托斯特尼筛法的具体过程如下：

列出2以后所有数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
记录素数2，由2²=4开始划去2的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
记录下一素数3，由3²=9开始划去3的倍数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
下一素数5，而5²=25>18，故剩余所有未标记的数皆为素数：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

改进过的埃拉托斯特尼筛法的算法伪代码如下表示：

输入：整数 \(n > 1\)

设 \(A\) 为布尔值数组，下标是 \(2\) 至 \(n\) 的整数，初始时全部设成 True。
for \(i = 2, 3, 4, ...\), 不超过\(\sqrt {n}\)：
\(\qquad\)if \(A[i]\) 为 True：
\(\qquad\)\(\qquad\)for \(j = i^2, i^2+i, i^2+2i, i^2+3i, ...,\) 不超过 \(n\) ：
\(\qquad\)\(\qquad\)\(\qquad\)\(A[j]\) := False

输出：使 \(A[i]\) 为 True 的所有 \(i\)。

结合前面的讲解，可以很容易理解到，伪代码中内循环的 \(A[j]\) := False 语句就是从每个确认的素数的平方开始划去其倍数的操作。我们也能很轻松地将这段伪代码转换成 Python 函数实现

# Method 4: Sieve of Eratosthenes
# It is one of the most efficient ways to find all of the smaller primes.
# Reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def get_prime_soe(n):
    prime_flags = [True] * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if prime_flags[i]:
            for j in range(i * i, n + 1, i):
                prime_flags[j] = False
    return [x for x in range(2, n + 1) if prime_flags[x]]

如何计算埃拉托斯特尼筛法的时间复杂度呢？无疑这取决于嵌套的两个for循环内的操作。操作的计数表达式是 \[\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \cdots = n × (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \cdots )\] 括号中是素数的倒数之和，也被称为素数调和级数（prime harmonic series）。数学上有严格证明素数调和级数趋近于 \(\log(\log n)\)，所以埃拉托斯特尼筛法的时间复杂度就是 \({\displaystyle O(n\log(\log n))}\)

性能比较

前述的四种搜寻不大于特定数的素数的方法，最慢的是朴素试除法，最快的应该是埃氏筛。我们可以用下面的测试程序比较它们的性能

assert get_prime_naive(10) == [2, 3, 5, 7]
assert get_prime_naive(100) == get_prime_halfway(100)
assert get_prime_halfway(1000) == get_prime_regular(1000)
assert get_prime_regular(10000) == get_prime_soe(10000)

print("Load\tSlowest\tSlower\tRegular\tFast\tSpeedup\n" + "-" * 50)
repeat = 10
for load in [256, 1024, 4096, 16384]:
    t_slowest = timeit(lambda: get_prime_naive(load), number=repeat)
    t_slower = timeit(lambda: get_prime_halfway(load), number=repeat)
    t_regular = timeit(lambda: get_prime_regular(load), number=repeat)
    t_fast = timeit(lambda: get_prime_soe(load), number=repeat)
    speedup = t_slowest // t_fast
    print(f"{load}\t{t_slowest:.5f}\t{t_slower:.5f}\t{t_regular:.5f}\t{t_fast:.5f}\t{speedup:.0f}")

t_fast = timeit(lambda: get_prime_soe(1000000), number=repeat)
assert len(get_prime_soe(1000000)) == 78498
t_average = t_fast / repeat
print(f"\nTime taken to find all prime numbers less than 1 million: {t_fast:.5f}s")

程序说明：

开始的四个断言assert语句核对朴素试除法的结果并与其他三个函数实现交叉验证。
后面的for循环依次逐渐增大工作量load，循环内调用 Python 的timeit工具测量重复10次的总运行时间，输出每一种方法的结果以及加速比（最慢方法的用时除以最快方法的用时）。
最后测试用埃氏筛方法计算一百万以内素数的数目，验证结果并打印用时。

在 MacBook Pro 2019 笔记本电脑上，测试程序的示例输出如下

Load	Naive	HalfWay Regular	SoE 	Speedup
-----------------------------------------------
256     0.00330	0.00241	0.00146	0.00022 14
1024	0.04203	0.02125	0.00577	0.00093 45
4096	0.58356	0.27865	0.02709	0.00401 145
16384	8.04601	3.90425	0.14061	0.01653 486

Time taken to find all prime numbers less than 1 million: 1.16481s

测试结果与算法分析一致。最慢的是朴素试除法，折半试除法次慢。常规试除法是判定单个数素性的最好方法，而埃氏筛是搜寻不大于特定数的全部素数的最高效方法。还可以看到，埃氏筛对比朴素试除法的加速比，随着工作量的增长也相应增长。这对应二者时间复杂度 \({\displaystyle O(n\log(\log n))}\) 与 \(O(n^2)\) 的比例关系。

用埃氏筛方法计算出一百万以内素数的数目为 78498，用时不到两秒。这个效率是惊人的，这就是算法的力量！

大素数验证

试除法和埃拉托斯特尼筛法都是素数判定的确定型算法。它们能给出确定的结果，但通常较慢。对于使用大素数的应用，如 2048 比特位的 RSA 模数 \(N\)（\(N=pq\)），两个素因子 \(p\) 和 \(q\) 都在 1024 比特位左右。对这么大的数执行确定型算法是不现实的，这时就需要快速的随机化算法。最常用的随机化算法就是费马素性检验和米勒-拉宾素性检验。

费马素性检验

根据费马小定理：对于一个素数\(n\) ，如果整数\(a\)不是\(n\)的倍数，则有\(a^{n-1}\equiv 1\pmod n\)。如果我们想知道\(n\)是否是素数，可以在区间\([2, n-2]\)中选取\(a\)，看看上面等式是否成立。如果对于数值\(a\)等式不成立，那么\(n\)是合数。如果有很多的\(a\)能够使等式成立，那么\(n\)可能是素数。

显然，选取\(a\)做检验的次数越多，等式成立时\(n\)是素数的概率越高。此算法伪代码如下所示

输入：\(n\)需要检验的数；\(k\)：检验次数。
重复\(k\)次：
\(\qquad\)在\([2, n − 2]\)范围内随机选取\(a\)
\(\qquad\)如果 \(a^{n − 1}\mod n ≠ 1\)，那么返回合数
返回可能是素数
输出：当\(n\)是合数时输出合数，否则输出可能是素数

因为在算法中使用了随机函数选取\(a\)，所以这是一种随机化算法。参考上面的伪代码，可以很容易地得到 Python 语言实现的费马素性检验函数

import random

def ferma_primality_check(n, k=5):
    """费马素性检验
    参数:
        n: 要检测的数字
        k: 检验次数（次数越多，准确率越高）
    返回:
        如果是可能的素数，返回True；如果确定是合数，返回False
    """
    if n <= 1:
        return False
    if n <= 3:
        return True

    for _ in range(k):
        # 随机选择一个[2, n-2]之间的整数
        a = random.randint(2, n - 2)
        # 根据费马小定理
        if pow(a, n - 1, n) != 1:
            return False  # 确定是合数
    return True  # 可能是素数

注意⚠️：费马小定理给出的是关于素数判定的必要但不充分条件。只能说检验重复次数越多，则被检验数是素数的概率越大。在使用模幂运算（Python 的pow函数所支持）的前提下，费马素性检验的时间复杂度是\(O(k \log^2n \log \log n)\)。这是非常快的。

米勒-拉宾素性检验

米勒-拉宾素性检验²，是当前普遍使用的一种素数判定法则。它利用随机化算法判断一个数是合数还是可能是素数。虽然同样基于费马小定理，米勒-拉宾素性检验比费马素性检验效率高得多。在展示米勒-拉宾素性检验的 Python 实现之前，简要介绍一下其工作原理。

从费马小定理出发，如果\(n>2\)，\(n-1\)是一个偶数，一定可以被表示为\(2^{s}*d\)的形式，\(s\)和\(d\)都是正整数且\(d\)是奇数。由此得到 \[a^{2^{s}*d}\equiv 1\pmod n\] 这时如果不断对上式左边取平方根再取模，总会得到\(1\)或\(-1\)³。如果得到了\(-1\) ，意味着下面②式成立；如果从未得到\(-1\)，则①式成立： \[a^{d}\equiv 1{\pmod {n}}{\text{ ①}}\] \[a^{2^{r}d}\equiv -1{\pmod {n}}{\text{ ②}}\] 其中\(r\)是位于\([0, s-1]\)区间的某个整数。所以，如果\(n\)是大于\(2\)的素数，一定有①或②式成立。这一规律的逆否命题也为真，即如果我们能找到这样一个\(\pmb{a}\)，使得对任意\(\pmb{0\leq r\leq s-1}\)以下两个式子均满足： \[\pmb{a^{d}\not \equiv 1\pmod n}\] \[\pmb{a^{2^{r}d}\not \equiv -1\pmod n}\] 那么\(\pmb{n}\)一定不是一个素数。这就是米勒-拉宾素性测试的机理。对于待测数\(n\)，算出\(s\)和\(d\)的值后，随机选取基数\(a\)，迭代检测以上两式。如果都不成立，\(n\)为合数，否则\(n\)可能为素数。重复这一过程，\(n\)为真素数的概率会越来越大。计算表明，经过\(k\)轮测试，米勒-拉宾素性检验的差错率最高不超过\(4^{-k}\)。

Python实现的米勒-拉宾素性检验函数如下，代码中的变量n,s,d,k与上面的说明对应：

def miller_rabin_primality_check(n, k=20):
    '''Miller-Rabin Primality Test wwith specified round of test 
    Input:
        n - n > 3, an odd integer to be tested for primality
        k - the number of rounds of testing to perfor
    Output:
        True  - passed (n is a strong probable prime)
        False - failed (n is a composite)'''
    
    # For a given odd integer n > 3, write n as (2^s)*d+1,
    # where s and d are positive integers and d is odd.
    assert n > 3
    if n % 2 == 0:
        return False
    
    s, d = 0, n - 1
    while d % 2 == 0:
        d >>= 1
        s += 1

    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(s):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            # The for loop did not encounter a break statement,
            # so it fails the test, it must be a composite
            return False

    # Passed the test, it is a strong probable prime
    return True

同样，基于模幂运算和多精度乘法，这个算法的时间复杂度是 \(O(k\log ^{3}n)\)。显然这也快于任何确定性算法。所以，在需要大素数的网络安全通信应用中，常常先用费马素性检验方法作预测试，而后调用效率更高的米勒-拉宾素性测试以保证高准确度。比如早先流行的加密通讯程序 PGP 及其同类的开源工具 GnuPG（GPG），就是如此验证随机生成的大素数的。

力扣题解

了解费马素性检验和米勒-拉宾素性检验的知识，可以展示求职者宽广的知识面，是绝好的加分项。在实际面试时，掌握常规试除法和埃拉托斯特尼筛法及其算法实现，就可以解决素数搜寻和验证相关的绝大多数问题了。下面给出力扣题库中的几道素数（质数）相关题目的分析和题解。

204. 计数素数

问题描述：给定整数 \(n\) ，返回所有小于非负整数 \(n\) 的素数的数量。
解题思路：这就是埃氏筛的直接应用，可以基本照搬前面get_prime_soe()函数的实现。不同点在于
1. 要求是计数所有小于输入 \(n\) 的素数，而前面函数对应的是不大于 \(n\) 的。
2. 要求输出计数值，而不是素数列表或数组。

示例代码：针对上述的不同点稍加调整，可得到如下 Python 实现

def countPrimes(n: int) -> int:
    if n < 3:
        return 0
        
    prime_flags = [True] * n
    for i in range(2, int(n ** 0.5) + 1):
        if prime_flags[i]:
            for j in range(i * i, n, i):
                prime_flags[j] = False
    
    return sum(prime_flags) - 2

说明一下，最后函数返回时减去2，是因为要排除头两项0和1，它们不是素数。

866. 回文素数

问题描述：给你一个整数 \(n\)，返回大于或等于 \(n\) 的最小回文素数。这里 \(1 ≤ n ≤ 10^8\)。
解题思路：首先要了解一个数学知识：除了11以外，偶数位的回文数都可以被11整除（比如1221）。因此我们可以只生成奇数位的回文数，然后用常规试除法判定是否为素数。还要单独考虑 n <= 11 时的特殊情况处理，这时返回值是回文素数数组 [2, 3, 5, 7, 11] 其中大于或等于 n 的数中最小的那一个。

示例代码：基于 Python 语言的解决方案如下

def primePalindrome(n: int) -> int:
    # 判断一个数是否为素数
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
    
    # 处理小于等于11的情况
    if n <= 11:
        for p in [2, 3, 5, 7, 11]:
            if p >= n:
                return p
    
    # 因为l=1的情况(个位数)已经在特殊情况中处理了，所以从l=2开始，
    # 使用高效方法生成奇数位回文数并检查是否为素数。
    for l in range(2, 6):  # 控制半部分长度，生成总共最多9位的回文
        # 生成半长度为l的所有数字
        for root in range(10 ** (l - 1), 10 ** l):
            s = str(root)
            pal = int(s + s[-2::-1])  # 生成奇数位回文（123 -> 12321）
            if pal >= n and is_prime(pal):
                return pal

程序说明：

出于模块化设计的思想，定义了is_prime()子函数实现常规试除法。
巧妙的奇数回文生成方式：利用s[-2::-1] 从倒数第二个字符开始的反向切片，然后与原数串联起来。如当 s = "123" 时，s[-2::-1] = "21"，s + s[-2::-1] = "12321"。这就是 l=3时生成的5位回文数。以此类推，l=5 生成9位回文数。

1175. 素数排列

问题描述：给定 \(n\)，返回将 1 到 \(n\) 的数字排列，使得素数在质数索引位置（从1开始计数）的排列总数，结果对 \(10^9 + 7\) 取模。
解题思路：首先找出前 \(n\) 个数中有多少个素数。设定有 \(p\) 个素数，合数的数目则为 \((n-p)\) 个。由此全部的排列方式为 \(p! * (n-p)!\)。

示例代码：直接将以上的解题思路变成 Python 程序就是

MOD = 10**9 + 7

def numPrimeArrangements(n: int) -> int:
       def is_prime(x):
           if x < 2:
               return False
           for i in range(2, int(x**0.5) + 1):
               if x % i == 0:
                   return False
               return True

       def factorial(x):
           res = 1
           for i in range(2, x + 1):
               res = (res * i) % MOD
           return res

       primes = sum(is_prime(i) for i in range(1, n+1))
       return (factorial(primes) * factorial(n - primes)) % MOD

程序说明：

子函数is_prime()和factorial()体现了模块化设计的思想。，is_prime()实现常规试除法，factorial()用for循环实现阶乘。
注意在factorial()子函数循环中每一步乘法的结果都对\(10^9 + 7\) 取模，这种操作用于在处理大数乘法时控制中间结果的大小，避免溢出。其数学原理是模运算的乘法同余性质，即恒等式 \[(a⋅b)\mod n=[(a\mod n)⋅(b\mod n)]\mod n\]

2523. 范围内最接近的两个质数

问题描述：给定一个区间 [left, right]，要求找出区间内相邻且差值最小的一对素数。如果不存在这样的素数对，则返回 [-1, -1]。
解题思路：先使用埃拉托斯特尼筛法高效地找出区间内所有素数，然后遍历所有相邻的素数对，计算它们的差值并记录具有最小差值的素数对。

示例代码：对原来的get_prime_soe()函数稍加调整，就可以实现对给定区间内所有素数的搜寻。后面用一个简单的for循环就可以计算和追踪相邻素数对的最小差值和该素数对本身。完整的 Python 程序如下

def closestPrimes(self, left: int, right: int) -> list[int]:
    MAX = right + 1
    is_prime = [True] * MAX
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX**0.5) + 1):
     if is_prime[i]:
         for j in range(i*i, MAX, i):
             is_prime[j] = False

 primes = [i for i in range(left, right + 1) if is_prime[i]]
 if len(primes) < 2:
     return [-1, -1]

 min_pair = [-1, -1]
 min_diff = float('inf')
 for i in range(1, len(primes)):
     if primes[i] - primes[i-1] < min_diff:
         min_diff = primes[i] - primes[i-1]
         min_pair = [primes[i-1], primes[i]]

 return min_pair

2761. 和等于目标值的素数对

问题描述：给定一个偶数 \(n\)，返回所有两个素数 \((x, y)\) 的组合，使得 \(x + y = n\) 且 \(x ≤ y\)。
解题思路：同样先使用埃拉托色尼筛法生成 \(n\) 以内所有素数，然后从最小的素数2开始遍历所有素数 \(p\)，如果 \(n-p\) 也是素数且满足 \(p <= n-p\)，将 \((p, n-p)\) 加入结果列表。注意遍历可以到 \(\lfloor\frac{n}{2}\rfloor\)为止，因为每个大于或等于 \(\frac{n}{2}\) 的 \(y\) 都对应一个小于或等于它的 \(x\)。

示例代码：以上的思路很清晰，转化成 Python 程序如下

def findPrimePairs(self, n: int) -> List[List[int]]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    res = []
    for i in range(2, n//2 + 1):
        if is_prime[i] and is_prime[n - i]:
            res.append([i, n - i])

    return res

埃拉托斯特尼（前276年—前194年），古希腊数学家、地理学家、诗人、天文学家和音乐理论家。他是已知的第一个计算出地球周长的人，其计算结果非常准确，误差率不到 1%。↩︎
卡内基梅隆大学的计算机系教授加里·米勒 (Gary Lee Miller) 首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的迈克尔·拉宾 (Michael O. Rabin) 教授作出修改，提出了不依赖于该假设的随机化算法。↩︎
这是因为从 \(x^2\equiv 1\pmod n\) 可以推导出 \((x-1)(x+1)=x^{2}-1\equiv 0\pmod n\)，又由于\(n\)是素数，根据欧几里得引理，它必然整除 \(x-1\) 和 \(x+1\)其中的一个，所以 \(x\bmod n\) 一定是 \(1\) 或 \(-1\)。↩︎