中午摸鱼的时候被一道算法题卡住了给定一段连续的数字区间要求找出区间内最大的质数。一开始我以为这不就是个带判断的倒序循环嘛真正动手之后才发现这件事背后牵扯到的数学和工程点比想象中多得多质数密度、筛法边界、确定性素性检验、模幂运算、步长设计还有一个特别容易翻车的边界条件处理。把这题完整啃下来之后我把它整理成了一套三段式方案倒序扫描、小质数哨兵过滤、米勒-拉宾精确判定。这篇文章就把完整思路、实现代码、优化细节和踩坑过程一次性讲清楚无论你是在准备算法面试还是想给某个需要快速找大质数的工具做底层支撑都能直接用上这套方案。1. 项目解读与整体方案1.1 题目到底想考什么先把这个题目翻译成人话输入一个区间[a, b]注意这里的“连续数字”就是连续正整数区间输出这个区间里最大的那个质数。如果没有质数返回空或抛错都可以但行为要明确。看起来很简单可一旦把数据范围拉到很大比如b达到10^12甚至10^18事情就不一样了。因为你需要在一个巨大的数字范围内定位一个质数而这个质数可能离范围上界很近也可能很远。如果老老实实把区间内每个数都做一次“从2试到sqrt(n)”的质数判断时间复杂度根本没法看。这道题真正考察的有三层第一层你能不能想到“找最大值”应该从大往小找而不是从小到大收集所有质数。第二层你会不会用一种快速且不会误判的方法来判断一个大整数是不是质数。第三层你知不知道怎么应对各种边界输入比如区间里恰好没有质数或者区间端点本身就小于2。1.2 为什么倒着找比正着找划算从小到大找质数通常做法是对整个区间做筛法得到区间内所有质数然后取最后一个。这个方案在区间不大、质数较多时没问题但它有一个明显的浪费为了得到“最后一个质数”你把前面所有质数都筛了一遍。从大往小找逻辑上完全反过来了。既然只要最大值那么从b开始向下逐个检查只要遇到第一个质数立刻就可以结束程序。这个思路建立在质数密度理论上对于接近b的数质数出现的密度大约是1 / ln(b)。比如b在10^12附近质数平均每二十几个数字就会出现一次就算运气差一点多检查几十次也就命中了。所以倒序扫描的时间成本主要不取决于区间有多长而取决于“上界附近质数离你有多远”。这比全区间筛法的复杂度低了好几个量级是这道题最核心的优化点。1.3 三段式方案的骨架我最终采用的方案分三段每段负责一个事第一段是预处理。把区间端点做裁剪和奇偶规整小于2的端点在入口直接处理。第二段是哨兵过滤。用一小张质数表比如[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]对候选数先做一次取模大部分合数在这一步就会被踢掉根本走不到昂贵的素性检验环节。第三段是精确检验。用确定性的米勒-拉宾算法用固定基集合保证 64 位整数范围内绝对不出错。这个设计最重要的特点是把“快速淘汰”和“精确判断”分成两层。不要一上来就对候选数跑米勒-拉宾那个函数对每个候选数都要做多次模幂运算虽然快但没必要让普通偶数、3的倍数、5的倍数去浪费它的时间。2. 核心算法原理拆解2.1 试除法是地基但不是全部判断一个数n是不是质数最朴素的方法是试除从2试到sqrt(n)只要发现一个因子就说明它是合数。这种方法在n很小的时候完全没问题但当n超过10^12sqrt(n)可能逼近百万甚至千万级别每判断一个候选数就是几百万次除法放在倒序扫描里完全不可接受。但试除法有个很好的变体只试除一组很小的质数。如果n能被其中任何一个整除那就直接判定为合数。由于越小的质数覆盖率越高用十几个小质数做一次取模已经能把绝大多数合数过滤掉。我实测下来的感受是这一步就像是安检口的第一道闸机它不需要对所有合数负责只需要把最“明显”的那一批筛掉把真正具备“质数嫌疑”的数交给后面的高级检查。2.2 确定性米勒-拉宾检验米勒-拉宾算法是一种概率型素性检验但通过固定基集合可以变成确定性算法适用某个特定数值范围。它判断一个奇数n是否为质数时会先把n - 1表示成d * 2^s的形式然后对若干基a做模幂运算观察结果是否满足特定条件。这里我先给出经过验证的固定基集合适用于n 2^64的全部整数2, 325, 9375, 28178, 450775, 9780504, 1795265022只要n小于2^64把这些基全部测一遍结论就是数学上确定的不会出现概率误判。这是它和随机基版本最大的不同随机基版本只能说“大概率是质数”确定性版本可以直接说“是质数”或“不是质数”。2.3 6k±1 和步长跳跃的数学依据所有大于3的质数都满足n mod 6 1或n mod 6 5也就是6k±1的形态。原因很简单任何整数被6除余数只可能是0、1、2、3、4、5。余数是0、2、4说明它是偶数余数是3说明它能被3整除这些数都不可能是大于3的质数。所以在倒序扫描时可以从上界向下只访问那些模6余1或余5的候选数把三分之二的奇数直接跳过。这个优化不复杂但在算法竞赛、嵌入式环境或者任何追求极致性能的场景里都是值钱的。3. 完整实现与代码详解3.1 快速幂取模先行米勒-拉宾的基础是模幂运算。直接算a^d mod n在d很大时不现实所以用快速幂把指数二进制展开边平方边取模把时间复杂度压到O(log d)。def qpow(a, d, n): res 1 a % n while d: if d 1: res (res * a) % n a (a * a) % n d 1 return res这段代码有一个容易忽略的细节进入函数之后立刻执行a % n。当基a比n大的时候先取模能显著降低后面乘法运算的规模。在 Python 这类大整数语言里乘法开销和数字长度强相关提前缩小数值就是提前省时间。3.2 Miller-Rabin 判断函数完整的确定性素性检测函数可以这样写def is_prime(n): if n 2: return False small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 bases [2, 325, 9375, 28178, 450775, 9780504, 1795265022] for a in bases: if a % n 0: continue x qpow(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我特别提醒一下return n p这行。它的含义是如果n能被某个小质数整除只有一种情况能通过检验即n自己就是那个小质数。比如n 2时走到p 4之前n % 2 0且n 2所以返回True。如果你漏掉这个判断直接返回False那么2这个最基础的质数就会被误判。3.3 区间最大质数主函数有了is_prime主函数的难点只在边界处理。我第一版写出来是有 bug 的问题就出在偶数端点和2这个特殊值上。后来修正成这样def max_prime_in_range(l, r): if r 2: return None if r 2: return 2 if l 2 else None if r % 2 0: r - 1 if l 2: l 2 while r l: if is_prime(r): return r r - 2 return None第一步处理r 2因为 2 是最小的质数范围上界都小于 2 的话根本不存在质数。第二步把r 2单独拎出来避免后续r % 2 0把2减成1从而漏掉这个最小的偶数质数。第三步把偶数上界降到最近的奇数。第四步规整下界。之后就进入普通倒序循环。3.4 各函数之间的衔接方式调用方式很简单print(max_prime_in_range(1, 100)) print(max_prime_in_range(100, 200)) print(max_prime_in_range(90, 96)) print(max_prime_in_range(7, 7))第二个例子会输出199第三个例子会输出空None因为90到96之间确实没有任何质数。第四个例子如果区间里只有一个数且是单点候选就按普通方式检测。整体架构不复杂但每一层都卡得挺准小质数过滤让大部分候选死在早期米勒-拉宾只对少数“嫌疑人”做深度审查倒序扫描保证我们在命中第一个质数时就终止。这样的结构不管后续要接批量查询还是做并行化都能平滑扩展。4. 边界情况与隐藏陷阱4.1 输入小于 2 的区间很多人在写这个题的时候默认输入是“正常”的正整数范围于是忘了处理0和1。0不是质数1也不是质数如果区间上界小于2结果一定是无解。我在主函数里用if r 2: return None把这个情况直接拦截掉避免后续代码拿着0或1进入素性检测。另一种情况是下界小于2但上界大于等于2比如[-5, 10]。这时候正确行为是自动把下界提升到2再继续找而不是报错。主函数里if l 2: l 2干的就是这件事。4.2 a 等于 b 时的单点检测区间只有一个数的时候问题就变成“这个数本身是不是质数”。这看起来简单但容易在倒序循环里被干死。比如max_prime_in_range(6, 6)第一版代码可能先把上界6减成5然后检查5但5已经超出原区间右边界了。这就会导致函数错误地返回5而不是告诉用户“区间内没有质数”。所以要明确一个原则对区间端点做的任何规整都不能突破原始区间边界。我的办法是在规整之前先把l也规整好然后把下界作为循环退出条件。只要r l搜索范围就在有效区间内。4.3 偶数、奇数、5的倍数的预处理倒序循环有一个非常实用的加速操作如果上界是偶数直接减1变成最大的奇数。这不会漏掉任何质数因为大于2的质数全是奇数。同理5的倍数除了5自身也都不可能是质数。所以很多人在循环里会加一句if r % 5 0: r - 2。但我要说明一点这行代码并不能保证安全跳过所有情况因为减2之后新的数有可能是偶数也有可能仍然能被5整除甚至可能小于下界。更稳妥的做法是只把它当做一个额外的快速拦截条件而不是跳步依据。也正因为这个原因我推荐的方案是让is_prime里的小质数表包含5。这样主循环保持最简洁的奇数步进合数过滤统统交给小质数表完成逻辑清晰也好调试。4.4 极大数下的溢出问题在 C/C 或 Java 这类固定位数的语言里res * a很容易在模幂运算中溢出尤其当n接近2^64时。即使最终结果要取模中间乘法也可能冲破数据上限造成结果错误而且这种错误往往非常隐蔽不那么容易发现。Python 的大整数没有溢出概念但性能会受损。所以我们在qpow里依然坚持每一步都取模而且乘之前先让每个因子都落在[0, n-1]区间。这个习惯写在 Python 里看似多余可一旦你把代码移植到别的语言或者改成某些嵌入式环境它就能避免一场灾难。5. 常见问题与性能排查5.1 米勒-拉宾会不会误判这是包在我身上的一次翻车前几天我用随机基版本测试n 3215031751它恰好是一个强伪素数某个随机基会把它误判成质数。换成上面那个固定基集合之后这种问题就彻底消失了因为它对2^64以下所有整数都有效。如果你的运行环境是 128 位整数或者需要测试更大的数那么就不能再用这七个基了。常见做法是把基底表换成针对 128 位的版本或者回到随机基并增加测试轮数。随机基依然有极小概率出错但可以通过多次测试把出错概率压到低于硬件故障率。5.2 步长设置为6之后会不会漏检有人会把倒序扫描的步长直接写成r - 6认为质数都是6k±1那么连续质数之间的差一定是6的倍数。这个想法是错的。反例随手就能举7和11都是质数但它们之间的差是4不是6。用固定步长6去扫会同时漏掉6k1和6k-1当中的一个形态。正确做法是先让候选数对齐到某个6k±1形态然后交替减2、减4或者干脆只按奇数步进用模6条件做过滤而不要用6作为固定步长。5.3 为什么大数上特别慢如果你发现代码在10^15级别的数字上明显卡顿通常不是因为米勒-拉宾本身慢而是在它之前缺少了小质数过滤。每个候选数都执行七次模幂运算和每个候选数先做十二次取模、把九成以上合数挡掉之后再做七次模幂运算整体时间能差出一个数量级。还有一个容易被忽略的问题当你打印日志时把大整数转成字符串本身就消耗 CPU再加上format操作会拖慢循环。调试阶段忍不住想打印候选值但在正式计算时把打印放在命中质数之后是基本的洁身自好。5.4 如何快速定位问题我排查这类算法问题时习惯用三组数据做回归测试。第一组是最小边界[1, 10]、[2, 2]、[3, 3]、[90, 96]。第二组是已知答案的整数区间[1000000000000, 1000000000100]可以提前用别的手段算好期望输出然后比对。第三组是同界点[999999999999999999, 1000000000000000000]专门考验大整数下边界处理是否稳。每改一次代码就跑一遍这三组能很快定位是数学判断的问题还是循环边界的问题。不要一上来就搓一个全区间暴力筛法做对照范围一大你连对照结果都等不出来。6. 复盘与后续扩展思路6.1 从单区间到批量查询的优化如果业务场景不是一个区间而是几十万个区间轮流查询单独跑这套函数也能完成任务但有更好的办法。比如先把所有查询的上界排序然后从小到大做一次分段筛法用筛出的质数去批量回答后续查询。这样能把多次重复的素性检测合并成一次区间筛。另外如果查询里经常出现同一个上界我建议给结果加一个缓存。用一个小字典记住(l, r)对应的结果下次再遇到相同的查询就直接返回。实测数据里这种缓存结构对重复性很强的业务压力能带来非常明显的吞吐提升。6.2 扩展到“连续数字串”场景还有一种玩法是把“连续数字”理解成一段很长的十进制数字串比如12345678910111213...让我找到这段数字串里所有连续子串中最大的质数。这个问题更有意思因为子串可能以0、2、4、5、6、8结尾也可以被快速否决但真正麻烦的是长子串的长度可能几百位。处理长数字子串时确定性米勒-拉宾的适用范围就失效了必须改用随机基版本并对同一个数测试足够多轮。这个场景也提醒我不要死守一个算法不放手先确认数据量级再决定用确定性方案还是概率性方案这是算法选型的基本功。6.3 几个值得保留的小技巧回头整理这次实践我格外想留三个技巧用在下一个项目里。一是把小质数过滤表尽量写长一点但也不要太长20个以内的小质数足够覆盖绝大多数合数再多就是边际收益递减。二是米勒-拉宾基表统一维护在一个常量里不要散落在深层代码中否则某天你想扩大到 128 位范围时会改得手忙脚乱。三是在任何主循环里宁可让代码多一行边界判断也不要依赖“输入都是合理数据”的上层约定因为算法的耐久度恰恰取决于它对意外输入的处理能力。这次做下来我最大的体会是一个看似“暴力可解”的数学题真正落地时会逼着你把筛法、素性检验、数论规律和工程边界全部过一遍。把这些点拆开逐个击破再组装成一条完整的流水线外面看起来只是一段不到一百行的代码里面装的却是实打实的经验和判断。希望这套拆解思路和代码方案也能让你的项目少踩几个坑。 
长河君 · 2026/10/20 15:44:52 · 阅读 1.2k 区间最大质数求解：Miller-Rabin素性检验与倒序扫描的优化实践
中午摸鱼的时候被一道算法题卡住了给定一段连续的数字区间要求找出区间内最大的质数。一开始我以为这不就是个带判断的倒序循环嘛真正动手之后才发现这件事背后牵扯到的数学和工程点比想象中多得多质数密度、筛法边界、确定性素性检验、模幂运算、步长设计还有一个特别容易翻车的边界条件处理。把这题完整啃下来之后我把它整理成了一套三段式方案倒序扫描、小质数哨兵过滤、米勒-拉宾精确判定。这篇文章就把完整思路、实现代码、优化细节和踩坑过程一次性讲清楚无论你是在准备算法面试还是想给某个需要快速找大质数的工具做底层支撑都能直接用上这套方案。1. 项目解读与整体方案1.1 题目到底想考什么先把这个题目翻译成人话输入一个区间[a, b]注意这里的“连续数字”就是连续正整数区间输出这个区间里最大的那个质数。如果没有质数返回空或抛错都可以但行为要明确。看起来很简单可一旦把数据范围拉到很大比如b达到10^12甚至10^18事情就不一样了。因为你需要在一个巨大的数字范围内定位一个质数而这个质数可能离范围上界很近也可能很远。如果老老实实把区间内每个数都做一次“从2试到sqrt(n)”的质数判断时间复杂度根本没法看。这道题真正考察的有三层第一层你能不能想到“找最大值”应该从大往小找而不是从小到大收集所有质数。第二层你会不会用一种快速且不会误判的方法来判断一个大整数是不是质数。第三层你知不知道怎么应对各种边界输入比如区间里恰好没有质数或者区间端点本身就小于2。1.2 为什么倒着找比正着找划算从小到大找质数通常做法是对整个区间做筛法得到区间内所有质数然后取最后一个。这个方案在区间不大、质数较多时没问题但它有一个明显的浪费为了得到“最后一个质数”你把前面所有质数都筛了一遍。从大往小找逻辑上完全反过来了。既然只要最大值那么从b开始向下逐个检查只要遇到第一个质数立刻就可以结束程序。这个思路建立在质数密度理论上对于接近b的数质数出现的密度大约是1 / ln(b)。比如b在10^12附近质数平均每二十几个数字就会出现一次就算运气差一点多检查几十次也就命中了。所以倒序扫描的时间成本主要不取决于区间有多长而取决于“上界附近质数离你有多远”。这比全区间筛法的复杂度低了好几个量级是这道题最核心的优化点。1.3 三段式方案的骨架我最终采用的方案分三段每段负责一个事第一段是预处理。把区间端点做裁剪和奇偶规整小于2的端点在入口直接处理。第二段是哨兵过滤。用一小张质数表比如[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]对候选数先做一次取模大部分合数在这一步就会被踢掉根本走不到昂贵的素性检验环节。第三段是精确检验。用确定性的米勒-拉宾算法用固定基集合保证 64 位整数范围内绝对不出错。这个设计最重要的特点是把“快速淘汰”和“精确判断”分成两层。不要一上来就对候选数跑米勒-拉宾那个函数对每个候选数都要做多次模幂运算虽然快但没必要让普通偶数、3的倍数、5的倍数去浪费它的时间。2. 核心算法原理拆解2.1 试除法是地基但不是全部判断一个数n是不是质数最朴素的方法是试除从2试到sqrt(n)只要发现一个因子就说明它是合数。这种方法在n很小的时候完全没问题但当n超过10^12sqrt(n)可能逼近百万甚至千万级别每判断一个候选数就是几百万次除法放在倒序扫描里完全不可接受。但试除法有个很好的变体只试除一组很小的质数。如果n能被其中任何一个整除那就直接判定为合数。由于越小的质数覆盖率越高用十几个小质数做一次取模已经能把绝大多数合数过滤掉。我实测下来的感受是这一步就像是安检口的第一道闸机它不需要对所有合数负责只需要把最“明显”的那一批筛掉把真正具备“质数嫌疑”的数交给后面的高级检查。2.2 确定性米勒-拉宾检验米勒-拉宾算法是一种概率型素性检验但通过固定基集合可以变成确定性算法适用某个特定数值范围。它判断一个奇数n是否为质数时会先把n - 1表示成d * 2^s的形式然后对若干基a做模幂运算观察结果是否满足特定条件。这里我先给出经过验证的固定基集合适用于n 2^64的全部整数2, 325, 9375, 28178, 450775, 9780504, 1795265022只要n小于2^64把这些基全部测一遍结论就是数学上确定的不会出现概率误判。这是它和随机基版本最大的不同随机基版本只能说“大概率是质数”确定性版本可以直接说“是质数”或“不是质数”。2.3 6k±1 和步长跳跃的数学依据所有大于3的质数都满足n mod 6 1或n mod 6 5也就是6k±1的形态。原因很简单任何整数被6除余数只可能是0、1、2、3、4、5。余数是0、2、4说明它是偶数余数是3说明它能被3整除这些数都不可能是大于3的质数。所以在倒序扫描时可以从上界向下只访问那些模6余1或余5的候选数把三分之二的奇数直接跳过。这个优化不复杂但在算法竞赛、嵌入式环境或者任何追求极致性能的场景里都是值钱的。3. 完整实现与代码详解3.1 快速幂取模先行米勒-拉宾的基础是模幂运算。直接算a^d mod n在d很大时不现实所以用快速幂把指数二进制展开边平方边取模把时间复杂度压到O(log d)。def qpow(a, d, n): res 1 a % n while d: if d 1: res (res * a) % n a (a * a) % n d 1 return res这段代码有一个容易忽略的细节进入函数之后立刻执行a % n。当基a比n大的时候先取模能显著降低后面乘法运算的规模。在 Python 这类大整数语言里乘法开销和数字长度强相关提前缩小数值就是提前省时间。3.2 Miller-Rabin 判断函数完整的确定性素性检测函数可以这样写def is_prime(n): if n 2: return False small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 bases [2, 325, 9375, 28178, 450775, 9780504, 1795265022] for a in bases: if a % n 0: continue x qpow(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我特别提醒一下return n p这行。它的含义是如果n能被某个小质数整除只有一种情况能通过检验即n自己就是那个小质数。比如n 2时走到p 4之前n % 2 0且n 2所以返回True。如果你漏掉这个判断直接返回False那么2这个最基础的质数就会被误判。3.3 区间最大质数主函数有了is_prime主函数的难点只在边界处理。我第一版写出来是有 bug 的问题就出在偶数端点和2这个特殊值上。后来修正成这样def max_prime_in_range(l, r): if r 2: return None if r 2: return 2 if l 2 else None if r % 2 0: r - 1 if l 2: l 2 while r l: if is_prime(r): return r r - 2 return None第一步处理r 2因为 2 是最小的质数范围上界都小于 2 的话根本不存在质数。第二步把r 2单独拎出来避免后续r % 2 0把2减成1从而漏掉这个最小的偶数质数。第三步把偶数上界降到最近的奇数。第四步规整下界。之后就进入普通倒序循环。3.4 各函数之间的衔接方式调用方式很简单print(max_prime_in_range(1, 100)) print(max_prime_in_range(100, 200)) print(max_prime_in_range(90, 96)) print(max_prime_in_range(7, 7))第二个例子会输出199第三个例子会输出空None因为90到96之间确实没有任何质数。第四个例子如果区间里只有一个数且是单点候选就按普通方式检测。整体架构不复杂但每一层都卡得挺准小质数过滤让大部分候选死在早期米勒-拉宾只对少数“嫌疑人”做深度审查倒序扫描保证我们在命中第一个质数时就终止。这样的结构不管后续要接批量查询还是做并行化都能平滑扩展。4. 边界情况与隐藏陷阱4.1 输入小于 2 的区间很多人在写这个题的时候默认输入是“正常”的正整数范围于是忘了处理0和1。0不是质数1也不是质数如果区间上界小于2结果一定是无解。我在主函数里用if r 2: return None把这个情况直接拦截掉避免后续代码拿着0或1进入素性检测。另一种情况是下界小于2但上界大于等于2比如[-5, 10]。这时候正确行为是自动把下界提升到2再继续找而不是报错。主函数里if l 2: l 2干的就是这件事。4.2 a 等于 b 时的单点检测区间只有一个数的时候问题就变成“这个数本身是不是质数”。这看起来简单但容易在倒序循环里被干死。比如max_prime_in_range(6, 6)第一版代码可能先把上界6减成5然后检查5但5已经超出原区间右边界了。这就会导致函数错误地返回5而不是告诉用户“区间内没有质数”。所以要明确一个原则对区间端点做的任何规整都不能突破原始区间边界。我的办法是在规整之前先把l也规整好然后把下界作为循环退出条件。只要r l搜索范围就在有效区间内。4.3 偶数、奇数、5的倍数的预处理倒序循环有一个非常实用的加速操作如果上界是偶数直接减1变成最大的奇数。这不会漏掉任何质数因为大于2的质数全是奇数。同理5的倍数除了5自身也都不可能是质数。所以很多人在循环里会加一句if r % 5 0: r - 2。但我要说明一点这行代码并不能保证安全跳过所有情况因为减2之后新的数有可能是偶数也有可能仍然能被5整除甚至可能小于下界。更稳妥的做法是只把它当做一个额外的快速拦截条件而不是跳步依据。也正因为这个原因我推荐的方案是让is_prime里的小质数表包含5。这样主循环保持最简洁的奇数步进合数过滤统统交给小质数表完成逻辑清晰也好调试。4.4 极大数下的溢出问题在 C/C 或 Java 这类固定位数的语言里res * a很容易在模幂运算中溢出尤其当n接近2^64时。即使最终结果要取模中间乘法也可能冲破数据上限造成结果错误而且这种错误往往非常隐蔽不那么容易发现。Python 的大整数没有溢出概念但性能会受损。所以我们在qpow里依然坚持每一步都取模而且乘之前先让每个因子都落在[0, n-1]区间。这个习惯写在 Python 里看似多余可一旦你把代码移植到别的语言或者改成某些嵌入式环境它就能避免一场灾难。5. 常见问题与性能排查5.1 米勒-拉宾会不会误判这是包在我身上的一次翻车前几天我用随机基版本测试n 3215031751它恰好是一个强伪素数某个随机基会把它误判成质数。换成上面那个固定基集合之后这种问题就彻底消失了因为它对2^64以下所有整数都有效。如果你的运行环境是 128 位整数或者需要测试更大的数那么就不能再用这七个基了。常见做法是把基底表换成针对 128 位的版本或者回到随机基并增加测试轮数。随机基依然有极小概率出错但可以通过多次测试把出错概率压到低于硬件故障率。5.2 步长设置为6之后会不会漏检有人会把倒序扫描的步长直接写成r - 6认为质数都是6k±1那么连续质数之间的差一定是6的倍数。这个想法是错的。反例随手就能举7和11都是质数但它们之间的差是4不是6。用固定步长6去扫会同时漏掉6k1和6k-1当中的一个形态。正确做法是先让候选数对齐到某个6k±1形态然后交替减2、减4或者干脆只按奇数步进用模6条件做过滤而不要用6作为固定步长。5.3 为什么大数上特别慢如果你发现代码在10^15级别的数字上明显卡顿通常不是因为米勒-拉宾本身慢而是在它之前缺少了小质数过滤。每个候选数都执行七次模幂运算和每个候选数先做十二次取模、把九成以上合数挡掉之后再做七次模幂运算整体时间能差出一个数量级。还有一个容易被忽略的问题当你打印日志时把大整数转成字符串本身就消耗 CPU再加上format操作会拖慢循环。调试阶段忍不住想打印候选值但在正式计算时把打印放在命中质数之后是基本的洁身自好。5.4 如何快速定位问题我排查这类算法问题时习惯用三组数据做回归测试。第一组是最小边界[1, 10]、[2, 2]、[3, 3]、[90, 96]。第二组是已知答案的整数区间[1000000000000, 1000000000100]可以提前用别的手段算好期望输出然后比对。第三组是同界点[999999999999999999, 1000000000000000000]专门考验大整数下边界处理是否稳。每改一次代码就跑一遍这三组能很快定位是数学判断的问题还是循环边界的问题。不要一上来就搓一个全区间暴力筛法做对照范围一大你连对照结果都等不出来。6. 复盘与后续扩展思路6.1 从单区间到批量查询的优化如果业务场景不是一个区间而是几十万个区间轮流查询单独跑这套函数也能完成任务但有更好的办法。比如先把所有查询的上界排序然后从小到大做一次分段筛法用筛出的质数去批量回答后续查询。这样能把多次重复的素性检测合并成一次区间筛。另外如果查询里经常出现同一个上界我建议给结果加一个缓存。用一个小字典记住(l, r)对应的结果下次再遇到相同的查询就直接返回。实测数据里这种缓存结构对重复性很强的业务压力能带来非常明显的吞吐提升。6.2 扩展到“连续数字串”场景还有一种玩法是把“连续数字”理解成一段很长的十进制数字串比如12345678910111213...让我找到这段数字串里所有连续子串中最大的质数。这个问题更有意思因为子串可能以0、2、4、5、6、8结尾也可以被快速否决但真正麻烦的是长子串的长度可能几百位。处理长数字子串时确定性米勒-拉宾的适用范围就失效了必须改用随机基版本并对同一个数测试足够多轮。这个场景也提醒我不要死守一个算法不放手先确认数据量级再决定用确定性方案还是概率性方案这是算法选型的基本功。6.3 几个值得保留的小技巧回头整理这次实践我格外想留三个技巧用在下一个项目里。一是把小质数过滤表尽量写长一点但也不要太长20个以内的小质数足够覆盖绝大多数合数再多就是边际收益递减。二是米勒-拉宾基表统一维护在一个常量里不要散落在深层代码中否则某天你想扩大到 128 位范围时会改得手忙脚乱。三是在任何主循环里宁可让代码多一行边界判断也不要依赖“输入都是合理数据”的上层约定因为算法的耐久度恰恰取决于它对意外输入的处理能力。这次做下来我最大的体会是一个看似“暴力可解”的数学题真正落地时会逼着你把筛法、素性检验、数论规律和工程边界全部过一遍。把这些点拆开逐个击破再组装成一条完整的流水线外面看起来只是一段不到一百行的代码里面装的却是实打实的经验和判断。希望这套拆解思路和代码方案也能让你的项目少踩几个坑。