“素数判定”这四个字在数学爱好者和做工程的人眼里完全是两回事。前者关心的是“这个数到底是不是素数”答案是一个布尔值后者关心的是“判定要花多久”因为素性检测往往出现在循环体内部慢一秒就是整个流程慢一秒。这些年我在几个项目和练习题里反复撞过墙最大的体会是素数判定看起来公式简单真正写出来的代码却经常藏着性能问题甚至逻辑错误。这篇文章会把试除法、筛法、大数概率检测这条路线完整串一遍把每个方案的复杂度、适用边界和踩坑点讲清楚既能给刚入门的人当实践笔记也能让已经写过代码的人重新检查自己的实现。1. 素性判定先搞清楚这个“简单问题”卡在哪1.1 数学定义只有一句话工程代价却差异巨大素数的定义确实很简单一个大于 1 的自然数如果除了 1 和它本身之外没有其他正因数就称为素数。反过来说只要找到任何一个大于 1 且小于它本身的因数就能立刻判定它是合数。这个判定逻辑本身没有任何争议真正的麻烦来自于“找到这个因数要花多久”。最直接的做法是从 2 一直试到 n-1只要某个数能整除 n就返回合数。这个思路叫作试除法它在概念上无可挑剔在性能上却经常让人崩溃。举一个具体数字如果要判断 10 的 12 次方附近的数试除到平方根大约是 100 万次除法这对现代 CPU 来说只是眨眼之间但如果把规模提升到 10 的 18 次方试除到平方根就是 10 亿次除法单线程跑下来要好几秒甚至更久。之所以要强调这一点是因为很多新手把“判定一个数是否素数”当成单次操作来思考而工程里的真实场景往往是批量判定生成随机密钥时要连续找几百个候选素数数学竞赛和算法题里要判定一段区间内所有数这些场景叠加起来复杂度就会从“毫秒级”变成“分钟级”。我在某项目里第一次写密钥生成逻辑时就是用最朴素的试除法硬扛结果一组参数要跑十几秒当时还以为是大整数运算的问题后来仔细分析才发现瓶颈全在素性检测上。1.2 试除法是必修课但别把它当万能钥匙试除法最大的优点是正确且容易验证。只要遍历到 n 的平方根还没有找到因数就可以断定 n 是素数。这里的关键是上界如果 n 是合数那么它一定可以分解成两个大于 1 的因数 a 和 b其中必然有一个小于等于 n 的平方根否则 a×b 会大于 n。所以只需要检查从 2 到 sqrt(n) 范围内的数不需要真的试到 n-1。我第一次认真算这个账的时候才发现之前写过的不少代码都在白白浪费计算量。有人写循环到 n/2有人写循环到 n这些写法在 n 是几百万的时候还能忍一旦 n 达到 10 的 12 次方以上和 sqrt(n) 相比会差出百万倍的性能差距。但试除法真正的瓶颈并不是上界而是它需要逐个测试的候选因数太多。即使只检查到平方根对于 10 的 18 次方量级的数仍然需要大约 10 亿次取模运算这个成本在大多数实际场景里不可接受。所以试除法适合“判断一个较小的数”或者“确认一个候选大素数的前期筛选”如果要把大数判定做到秒级必须换更聪明的算法。2. 从小数到大数试除法优化与筛法批量判定2.1 试除法的三档优化先排除偶数再压缩步长在正式走向大数算法之前值得把试除法榨到极致因为很多场景下优化后的试除法已经足够用。第一档优化是提前处理 2。偶数除了 2 以外都不是素数所以可以先判断 n 是否等于 2如果 n 是偶数且大于 2 直接返回合数。这样后续循环只需要处理奇数候选因数数量直接减半。第二档优化是只检查到 sqrt(n)。这个前面已经解释过是正确性的关键也是性能提升最大的部分。第三档优化是步长压缩。奇数序列里仍然混着大量 3 的倍数如果我们已经单独验证过 3那么真正需要检查的只可能是模 6 余 1 或模 6 余 5 的数。可以用一个固定模式d 从 5 开始每次加 6同时检查 d 和 d2。这个技巧的本质是跳过所有被 2 和 3 整除的数代码也不复杂。def is_prime_by_trial(n): if n 2: return False for p in (2, 3): if n % p 0: return n p d 5 while d * d n: if n % d 0 or n % (d 2) 0: return False d 6 return True这段代码的正确性很好验证5、7、11、13、17、19……正好覆盖了所有不是 2 和 3 倍数的候选数。实际测下来它比朴素试除法在平均情况上快三倍左右编写成本又低很适合作为后续大数算法的“第一道安全闸门”。2.2 埃拉托色尼筛法批量判定素数的经典路径如果需求不是判定某一个数而是把一个区间内的素数全部找出来逐个数做试除法就显得很浪费。这时候埃拉托色尼筛法才是正确选择。筛法的思路非常直观初始化一个布尔数组假设 2 到 M 之间的所有数都是素数。从 2 开始把 2 的所有倍数全部标记为合数然后找到下一个未被标记的数 3把 3 的所有倍数标记为合数再下一个是 5以此类推。标记到平方根处就可以停因为一个合数必然有一个小于等于平方根的因数。我用 Python 写过很多次这个函数最简洁可靠的版本是这样的def sieve_of_eratosthenes(n): if n 2: return [] is_prime [True] * (n 1) is_prime[0] is_prime[1] False i 2 while i * i n: if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False i 1 return [x for x in range(n 1) if is_prime[x]]注意内层循环从 i×i 开始而不是从 2×i 开始。原因是对于每个小于 i 的因数它的倍数已经在更早的轮次里被标记过了。例如处理 7 的时候7×2、7×3、7×5 都已经分别被 2、3、5 标记过直接从 49 开始标记可以省掉大量重复操作。2.3 筛法的工程使用边界内存和分段筛法的问题在于内存。如果用一个字节表示一个数的状态筛到 10 的 7 次方只需要 10MB筛到 10 的 8 次方需要 100MB再往上翻就有点吃力了。我见过有人试图筛到 10 的 9 次方结果程序在初始化数组那一步就卡了几乎动不了。实际工程中常用的办法是分段筛法。设一个合理的内存块大小比如每次筛 100 万个数先用小筛子求出 sqrt(M) 以内的所有素数再用这些小素数去标记每一段的合数。这样既不浪费内存又能处理很大的上界。筛法的时间复杂度是 O(M log log M)在 M 不超过千万量级时它通常是批量生成素数的最快选择。判断“这个区间是不是都是合数”这类问题时筛完直接查表往往比逐个数做试除法快一个数量级以上。3. 大素数的快速判定不如用概率化检测来“提前止损”3.1 从同余定理到伪素数为什么逆命题不可靠当 n 变得足够大大到试除法完全跑不动时就必须换一种思路。数论里有一个非常有用的同余定理如果 p 是素数那么对任意与 p 互素的 aa 的 p-1 次方模 p 恒等于 1。这个定理本身是充分条件但很多人会误以为条件反过来也成立如果一个数 n 满足某个 a 的 n-1 次方模 n 等于 1就认为 n 可能是素数。这个推断在绝大多数情况下是对的但存在反例。经典的反例之一是 341它等于 11 乘以 31明显是合数却满足 2 的 340 次方模 341 等于 1。这类数被称为伪素数。更让人头疼的是所谓的“绝对伪素数”也叫卡迈克尔数例如 561、1105 这类数它们对任意与它互素的底数 a 都满足费马同余条件几乎可以说是“骗过了”最朴素的概率检测。所以直接用费马检测做素性判定在工程上是不够安全的。3.2 MR测试的步骤拆解把“平方根”这个线索用起来改进后的概率检测利用了另一个数学事实对于素数 n方程 x 的平方模 n 等于 1 的解只有两个那就是 1 和 n-1。但如果 n 是合数方程可能出现更多的解这些多出来的解就叫非平凡平方根。只要在检测过程中碰到了非平凡平方根就可以断定 n 是合数。MR 测试的具体做法是把 n-1 拆成 d 乘以 2 的 s 次方其中 d 为奇数。然后计算 a 的 d 次方模 n得到初始值 x。如果 x 等于 1 或 n-1当前底数通过检测。否则把 x 连续平方 s-1 次每次平方后检查是否等于 n-1如果出现了就通过如果一直没出现就说明 n 是合数。典型的实现如下def is_prime_mr(n, bases): if n 2: return False for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37): if n % p 0: return n p d n - 1 s 0 while d % 2 0: s 1 d // 2 for a in bases: if a % n 0: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True这段代码里的 pow(a, d, n) 是 Python 内置的模幂运算它比先算 a 的 d 次方再去取模要快得多也避免了中间结果爆炸。自己手写模幂时很容易在这里出错后面专门讲。3.3 底数选择不同位宽下的“确定性边界”MR 测试被称为概率算法是因为随机挑选底数时每次误判合数为素数的概率大约四分之一。但实际工程中我们几乎不会用完全随机的底数。对于固定位宽范围内的整数已经有人用穷举方式验证出了一些固定的底数组合只要 n 小于某个上界用这些底数测试就绝不会误判。下表给出几组常用的固定底数和它们经过验证的覆盖上界底数集合已验证的判定上界适用场景2, 7, 614,759,123,141覆盖 32 位无符号整数2, 3, 5, 7, 11, 13, 17341,550,071,728,321小于 3.4 乘以 10 的 14 次方2, 325, 9375, 28178, 450775, 9780504, 1795265022小于 2 的 64 次方覆盖 64 位整数用最后一组底数在 64 位范围内测试效果等同于确定性算法。超出这个范围才需要把它当概率算法用或者配合更多轮随机底数来降低错误率。这个表格我建议直接保存下来写代码时复制进去就行比自己临时挑底数要安全得多。4. 确定性检测与生产环境选型该手写时就手写该用库时就别折腾4.1 确定性算法在理论上重要工程上却很难用既然 MR 测试在 64 位范围内已经能做到“实际确定”为什么还需要研究真正的确定性算法因为更大的数比如 RSA 密钥生成里要用到的几百位十进制数没有现成的固定底数组合可以覆盖全部范围只能借助数学意义上的确定性检测算法。历史上确实出现过多项式时间的确定性素性检测算法它从理论上证明了素数判定属于多项式可解问题。但这类算法的常数很大实际运算特别慢工程中很少有人直接用。工程界的常见做法是在 2 的 64 次方以内用固定底数 MR超过这个范围则用“MR 多轮检测加 Lucas 类检测”的组合在一些成熟大数库里这种组合被认为对实际应用足够可靠但不会宣称是数学意义上的证明。4.2 不同规模下的推荐方案组合从我实际使用的经验来看可以按数字大小分层选择方案小于 1000 的数直接试除法快到不需要任何优化。小于 100 万的批量查询用埃拉托色尼筛法生成素数表。小于 2 的 64 次方的单次判定用固定底数 MR 测试。更大的数比如数百位十进制数用成熟库提供的高置信度概率检测通常内部会跑多轮 MR。这个分层方案的核心思想是不要用一把锤子敲所有钉子。试除法在小数字上最直观筛法在批量场景中平行优势巨大MR 则是中大规模的默认选择。4.3 我踩过一次的“手写库”教训有一年某项目要生成特定格式的大数参数我当时想省掉引入大数库的麻烦就自己在 C 代码里用数组模拟大整数并手写了模幂和 MR。功能倒是调试通过了但在随机性测试阶段发现因为我在某个细节里没有正确实现高精度乘法取模偶尔会把合数判成素数。排查了很久才发现是对中间结果的进位处理不正确。那次之后我学到的教训是素数判定这种逻辑正确性远比其他东西重要。如果只是在算法竞赛或者自己研究写的练习代码手写完全没有问题而且值得反复手写以理解原理。但如果是给生产业务用的代码还是应该优先用成熟的库例如大整数库和符号数学库里都提供了质量不错的素性检测函数。我的建议是手写版本用于学习和大部分中小规模场景生产环境的大数场景直接用库除非你的业务规模小到能严格覆盖验证边界。5. 常见问题与性能调优实录5.1 最危险的坑模乘中间结果溢出MR 测试里最核心的运算是模乘。在 Python 里这个问题被语言天然规避了因为 Python 的整数可以无限增长。但在 Java、C、C、JavaScript 这类语言里直接写 a×b%m 很有风险尤其 m 接近 2 的 63 次方时a×b 可能溢出变成负数再取模结果完全错误而且不是每次都能遇到调试极其痛苦。在 C 里优先使用编译器提供的 128 位整数类型using i64 long long; i64 mul_mod(i64 a, i64 b, i64 m) { return (i64)((__int128)a * b % m); }如果编译器不支持也可以把乘法拆成多次加法取模性能会慢一点但至少正确。JavaScript 里最稳妥的办法是遇到可能超界的数直接用 BigInt虽然速度不如 Number但不会错。不要小看这个细节。很多关于 MR 实现的讨论里最后发现问题都出在模乘上而不是算法本身逻辑上。我自己曾经用一个错误实现的模乘跑出了“561 被判断为素数”的荒谬结论后来排查代码才发现是溢出导致。5.2 第二个坑把筛法和单点判定混为一谈另一个常见问题是为了判断一个大数是否为素数先把从 2 到它平方根之间所有素数筛出来再拿这些素数区测试它。这个思路本身不矛盾但时间复杂度往往是灾难。筛法的目标是批量生成它把“标记”一次性做完后续查询就可以 O(1) 查表。而如果只做单个数判定筛法需要先构建一个巨大的布尔数组内存和时间都花得冤枉还不如直接用 MR。我在某次练习题里就犯了类似的错误为了判断一个大约 1000 位的候选数先尝试筛所有小于它平方根的素数结果内存直接爆掉。后来改成 MR 加快速整除小素数列表整个流程从跑不动变成毫秒级。这条经验可以总结成一句话先分清是“单点查询”还是“区间批量查询”再决定用筛法还是 MR。5.3 性能优化先用小素数列表“拦路”MR 测试虽然速度很快但每个候选数都要做若干次模幂运算。实际场景里更聪明的做法是在进入 MR 之前先拿一批小素数做预筛比如 2、3、5、7、11、13、17、19、23、29、31、37。如果候选数被其中任何一个整除直接判合数只有筛掉明显合数后才需要跑 MR。这样做虽然写起来多一行性能提升却很明显因为随机生成的候选数里有很大比例会被小素数整除。举个直观例子随机挑一个奇数大约三分之一会被 3 整除剩下的大约五分之一会被 5 整除经过 2、3、5、7、11、13 这连串检查后能进入 MR 的数只有很少一部分。把这个技巧用在密码学随机素数的生成里能把整体生成时间压下来不少。5.4 回归测试不能少边界用例漂亮才算通过我自己的习惯是任何素性检测函数写完先跑一遍固定测试集再投入使用。测试集至少要包含这些边界输入期望结果说明0、1合数最容易忽略的边界2、3素数最小的素数和奇素数边界9、15、49合数奇合数的典型例子561、1105合数卡迈克尔数能骗过朴素费马检测2 的 31 次方减 1素数较大的已知素数2 的 61 次方减 1素数超过 32 位范围的大素数因为素性检测不是那种“逻辑对了就能一劳永逸”的代码边界情况往往隐藏在语法的缝隙里。把这些用例写进测试每次修改实现后跑一遍能省下大量后面排查问题的时间。写在最后的经验做了这么多年和数字打交道的东西我个人对素数判定的态度是永远尊重“底数选择”和“整数溢出”这两个细节。很多看似复杂的实现最后出问题的地方都不是算法主逻辑而是那些你以为不会再回头看的基础运算。如果你刚接触这个问题建议按试除法、筛法、MR 测试这个顺序逐一亲手写一遍不要急着跳到最终代码。每一个阶段踩过的坑都会成为你后面判断方案好坏的直觉来源。将来遇到更大的数字或更苛刻的性能要求时你会感谢现在这个肯把每个细节抠明白的自己。