Java数论算法精讲：从素数筛到快速幂，破解笔试性能瓶颈

1. 先看透本质数论题在Java笔试中到底在考什么我在不少面试场合和代码评审里见过同一个场景一道题看起来只是普通数学计算比如“统计区间内质数的个数”“求两个超大数的最大公约数”甚至“计算某个数的N次幂结果”候选人明明逻辑写得很顺自测也对但一提交就超时或者内存爆掉。问题几乎都出在同一个地方——把数论题当成了循环题在做。Java面试里的数论问题本质上不是为了考数学定理的背诵能力而是考察你能不能在暴力解法之外找到一条利用数学性质压缩时间复杂度和空间复杂度的路径。“Java数据结构与算法”这套体系里数据结构是骨架算法是灵魂而数论是藏在算法背后的那双手——它让很多看起来需要跑几亿次的循环最终只需要跑几千次。我常说数论问题在Java里有两个核心考点一是对整数性质的敏感度比如奇偶、最大公约数、互质关系、模运算规律二是对Java语言特性的熟练度比如boolean[]数组的默认值、long类型的溢出边界、HashMap做缓存时键值对的选择。这两者缺一不可。举一个最常见的例子判断一个数是不是质数。最自然的写法是从2循环到n/2逐个取余。如果面试题只有一两个数这样写没毛病。但一旦变成“求出1到1000000之间所有质数”暴力循环的复杂度就变成了O(n²)跑起来直接超时。这时候埃拉托斯特尼筛法就是它的数学解药——用空间换时间用标记数组把复杂度砍到O(n log log n)。这就是数论的价值。在动手写代码之前我建议你先做一道简单的心理测试如果题目里出现了“质数”“公约数”“幂运算”“取模大数”这些词先停三秒别急着写循环。想一想这道题的数据范围是多少暴力解法的瓶颈在哪有没有某种数学结构能让重复计算直接消掉。这三个问题想清楚了后面每一步代码都是在给你自己省时间。2. 素数筛法不止于标记用Java数组优雅地处理边界素数问题是最常见的数论入门场景。先说埃拉托斯特尼筛法Sieve of Eratosthenes的落地写法它远比教科书里那几行伪代码要讲究。很多Java初学者第一次写筛法时都会碰到一个坑直接new boolean[n1]然后从2开始标记结果发现数组默认全是false判断逻辑反了。这里我建议直接用boolean[]配合Arrays.fill或者干脆用byte[]来节省内存因为Java的boolean[]底层其实占用一个字节而byte的读写性能在某些JVM版本里会更好。来看一段可以直接跑的筛法代码public static ListInteger sievePrimes(int n) { if (n 2) { return new ArrayList(); } byte[] isComposite new byte[n 1]; ListInteger primes new ArrayList(); for (int i 2; i n; i) { if (isComposite[i] 0) { primes.add(i); // 小心乘法溢出这里用long做临时运算 if ((long) i * i n) { for (long j (long) i * i; j n; j i) { isComposite[(int) j] 1; } } } } return primes; }第一眼看上去你可能觉得用isComposite[i] 0表示质数有点别扭但我特意这么写是因为byte[]默认就是0这样连Arrays.fill都省了。筛法启动的起点是i * i而不是2 * i这是一个非常关键的优化因为在到达i之前所有比i小的质因子已经筛过一轮了2*i、3*i这些位置早就是被标记过的合成数再筛一遍纯属浪费时间。这是数学性质在代码里的直接体现也是面试官最想看到你主动做的一层优化。再看边界问题。当n取到Integer.MAX_VALUE附近时n 1数组本身就可能让堆内存吃不消。实际业务里如果你要处理更大范围可以改用分段筛法segmented sieve把区间切成每段大小为sqrt(n)的窗口段内只保留当前窗口的标记数组。不过笔试和大部分规模可控的场景直接一次性筛出1到100000的质数表就够了。你甚至可以把这张质数表缓存成全局静态数据后续每个测试用例都直接查表这就是典型的“用空间换时间”思维和数据结构里的哈希表加速是同一个道理。最后提醒一个容易踩的坑筛法循环里做j i时j的类型最好用long避免i很大时i * i溢出int范围变成负数。这个问题我在真实项目里见过不止一次一旦溢出标记数组就全乱了而且极难排查。数论题最恶心的就是这种隐蔽的整数溢出问题它不会直接报错只会悄悄违反数学规则。3. 从辗转相除法到模逆元欧几里得算法家族的实战演进如果说素数筛法是为了解决“数量多”的问题那么欧几里得算法家族就是为解决“数字大”的问题而生的。最大公约数GCD几乎不用我多介绍公式就是gcd(a, b) gcd(b, a % b)Java标准库还贴心地提供了BigInteger.gcd()方法。但当问题从“求最大公约数”升级到“求模逆元”或者“解同余方程”你需要的就是扩展欧几里得算法Extended Euclidean Algorithm。扩展欧几里得算法在Java面试里经常以“实现一个函数传入两个整数返回它们的最大公约数以及一组系数使得ax by gcd(a, b)”的形式出现。难点在于Java是值传递递归返回时你没法直接把x和y带出来。常见的做法是定义一个辅助数组或者用一个简单的long[]作为参数容器。我这里推荐用long[]因为int在辗转相除过程中很容易溢出干脆起手就用long省得中途转型出错。public static long[] exgcd(long a, long b) { if (b 0) { return new long[]{a, 1, 0}; } long[] result exgcd(b, a % b); long gcd result[0]; long x1 result[1]; long y1 result[2]; // 关键数学推导x y1, y x1 - (a / b) * y1 return new long[]{gcd, y1, x1 - (a / b) * y1}; }这段代码背后的推导要比代码本身更值得吃透。设a bb a % b递归层返回的系数x1和y1满足a * x1 b * y1 gcd(a, b)。因为b a - (a / b) * b把这个代入原式整理后就能得到a和b前的系数正好是y1和x1 - (a / b) * y1。这个公式你要是用笔推导一遍记忆会深刻得多也不会跟人比谁代码背得熟。模逆元是什么简单说就是满足a * x ≡ 1 (mod m)的那个x。它有什么用实际场景里最常见的是做除法取模。普通的除法在计算机里做不到有小数精确取模但如果你手头有a对m的模逆元就能把“除以a再取模”巧妙转换成“乘以a的逆元再取模”整个过程完全避开除法和浮点运算。很多密码学算法、哈希散列、分布式ID生成底层都有模逆元的身影。具体怎么用扩展欧几里得算法求模逆元核心前提是a和m互质即gcd(a, m) 1否则逆元不存在。用刚刚的exgcd(a, m)拿到的x就是模逆元。要注意的是exgcd返回的x可能是负数Java里取模结果也允许负数所以最后必须手动修正成(x % m m) % m。这个“负数转正”的操作在数论题里非常常见我基本是条件反射式地写完exgcd立刻补一行取模修正因为后续用这个逆元做乘法时负数会引发你完全摸不着头脑的答案。4. 快速幂的二进制把戏让指数级问题从超时变秒出你迟早会碰到一类题底数很大、指数更大还要你对某个模数取余。最没悬念的写法当然是一个for循环连乘比如2^10000000。别说等它跑完光是long溢出就能让结果在某个瞬间变成负数。那正确的打开方式是什么快速幂Fast Exponentiation就是专门处理这个问题的它的思路值得你作为一种通用思维模型来记。核心思想很朴素把指数写成二进制形式比如x^13 x^(841) x^8 * x^4 * x^1。这就把原来要做13次乘法的问题压缩成了只需要做3次乘法加上指数分解。代码实现上我们只用循环不断把底数平方遇到当前二进制位为1就累乘进结果。配合% mod每一步都强制限制在模数范围内彻底避免溢出风险。public static long quickPow(long base, long exp, long mod) { long result 1 % mod; base % mod; while (exp 0) { if ((exp 1) 1) { result (result * base) % mod; } base (base * base) % mod; exp 1; } return result; }这里有几个细节。第一result的初始值为什么是1 % mod而不是1这是为了兼容mod 1这种极端情况如果模数是1任何整数对它取模都是0直接用1初始化会返回错误结果。第二base在进入循环前就要先% mod因为乘法的模等价于对每个因子取模后再相乘这不只是一个性能优化更是一个防溢出保险。第三exp 1相当于除以2但用位运算更快也更能体现你懂二进制层面的操作。我遇到过不少人在笔试里被快速幂卡住其实不是不知道算法而是没有习惯对mod做特殊处理。尤其是当模数很大时result * base本身就可能溢出long哪怕你已经取过模。这时候有两个办法一是用Math.multiplyHigh配合手工进位模拟128位乘法二是直接换BigInteger。从工程角度来看笔试时间有限直接用BigInteger的modPow方法反而更稳妥——它内部已经实现了快速幂而且不会溢出。但面试手写环节还是应该展示快速幂的裸实现并主动讲解溢出问题这能证明你是真的理解原理而不只是背API。快速幂的思想不只是用在幂运算上矩阵快速幂、斐波那契数列的第N项优化、以及很多递推公式的加速底层都是同一个二进制分解逻辑。可以说学会了快速幂你等于掌握了一把能撬动一大片复杂问题的杠杆。5. 数论与数据结构结合用Map、Set和缓存完成最后一击前面几章讲的都是数论算法本身但“Java数据结构与算法”这个题目里数据结构绝不只是陪跑配角。我特别想强调一个观点数论算法里的重复计算恰恰是数据结构大展身手的地方。最典型的例子是记忆化搜索。假设你写了一个递归版本的扩展欧几里得算法里面会大量出现相同参数的重复调用。这时候你可以在方法外面挂一个HashMapPair, Long[]每次进入递归先查表有就直接返回缓存没有才算完再存进去。这种“算法缓存”的组合在面试中叫做“自带剪枝的递归”它能把你原本的重复子树整个砍掉让时间复杂度的常数项大幅下降。注意这里我用的键是Pair或者干脆是(a,b)字符串拼接因为Java没有内置的二元组类你用List.of(a,b)当键虽然可行但哈希计算和内存开销都偏大手写一个record或直接拼字符串反而更实在。再举一个实际数据结构选型的例子。有一类题是“统计区间内有多少对互质的数”或者“根据质因数分解结果求约数个数”。暴力做法是双重循环遍历所有数字对然后对每一对再跑一遍GCD复杂度直接爆表。但如果把质因数分解后的结果存进一个HashMapInteger, Integer键是质因子值是出现次数后续很多判定就能通过查表完成而不是重复分解数。比如要判断两个数的最大公约数是否大于1直接比较它们的质因子集合是否有交集这比重新调用gcd快得多尤其当数字数量在百万级时差距可以到几十倍。还有一类问题是在线查询系统会不断问你“某个数字是否在之前出现过素因子为3”这时你可以维护一个HashSetInteger专门记录历史数据中出现过的素数因子。每次来一个新数字分解质因数后跟这个HashSet一比对就能在O(1)时间内给出答案。整个过程完全避开了“遍历历史数组”这种低效方案。用HashSet而不是ArrayList就是为了把查找从O(n)降到O(1)这就是数据结构对算法复杂度的实质贡献。最后说一个容易被忽略的小技巧数论题往往需要一张很大的质数表但Java里频繁创建大数组很慢。建议在类的静态块里预生成全局质数表后续所有方法直接引用。我习惯用static final int[] PRIMES配合静态初始化这样既能保证线程安全启动时只建一次又能在多线程并发调用时没有锁开销。笔试不讲究这个但如果放到生产环境里的推荐系统或风控规则引擎里全局缓存和静态初始化带来的性能收益是非常明显的。6. 做题顺序与复杂度节奏数论高手的实战复盘从筛法到扩展欧几里得再到快速幂和缓存组合这些技巧分散在不同场景里。但实际笔试时你面对的通常是一整套题混在一起怎么快速识别哪道题该用哪些数论技巧我总结一个自己的做题顺序未必适合所有人但参考价值很高。拿到题先看数据范围。如果数字上限在10的6次方级别筛法通常够用如果在10的9次方以上就要考虑分段筛法或者干脆用BigInteger。接着看操作类型是单次查询还是大量查询大量查询基本意味着必须预处理比如筛表、存GCD缓存单次查询则可以酌情直接算。再看模数的存在出现模数就要有取模防溢出的意识并检查是否涉及除法的模运算——只要涉及立刻想到模逆元。按这个顺序走下来你基本能把一道题从“数学题”成功转化成“数据结构题”也就是把抽象的数学关系转换成具体的数组索引、哈希键值、缓存节点。我在不少面试复盘里发现真正的分水岭不是谁记住了更多公式而是谁更早意识到“数学关系能映射为数据结构”。举个实际的例子。假设笔试有这么一道题给定一个长度很长的数组要求输出所有长度为3的子序列中三个数乘积可以被6整除的子序列个数。第一反应可能是三层循环枚举所有三元组时间复杂度O(n³)肯定会超时。但如果用数论思路能被6整除意味着至少包含因子2和因子3。你需要的只是统计整个数组里“偶数”“含因子3的数”“同时含2和3的数”各有多少然后用组合计数公式快速计算。这个统计过程只需要一次遍历配合若干计数器变量根本用不到复杂数据结构。但如果你不习惯从因子角度拆解问题就会陷进三重循环的泥潭。这类从“枚举所有可能”转向“统计特征分布”的思维正是数论和数据结构结合的真正价值。它考的不是你会不会写循环而是你会不会从更抽象的层面观察数据——这一步想通了代码往往只需要几十行。7. 工程化思维下的数论模块让算法代码变成可复用的资产聊完算法本身我想把视角拉到工程层面。很多Java开发者会把数论算法当成面试题库存用过就忘这其实非常可惜。因为数论算法在真实项目里的复用率比你想象的高得多。限流算法里的滑动窗口哈希、分布式系统中的一致性哈希、权限系统里的哈希散列、甚至日志追踪ID的生成背后都有数论影子。我自己习惯在项目里建一个NumberTheoryUtils工具类把所有经过验证的算法沉淀成静态方法比如sievePrimes、exgcd、quickPow、modInverse。每个方法都写上时间和空间复杂度注释以及输入参数的边界说明。这样下次某个业务模块想做幂等校验或者数据分片直接调用工具类就行不需要重新搜索CSDN或者翻笔记。这个习惯帮我省下来的时间远比当初整理那几十行代码付出的时间多。工程化还有一个好处可以写单元测试把边界条件钉死。数论算法最怕的是溢出和取模负数你可以在测试用例里故意放几个极端值比如Integer.MAX_VALUE、Long.MAX_VALUE、2^31 - 1。跑通一次以后无论算法怎么重构都有测试兜底。这种“算法工程规范”的组合才是真正能称为资产的东西。顺带说一句Java 17里推出了record特性非常适合用来当缓存Key或者返回多值结果。比如扩展欧几里得的返回值可以定义成record ExgcdResult(long gcd, long x, long y)可读性比long[]好得多。我现在的代码风格已经全面转向这种类型安全、自带toString的写法读代码的人再也不用猜数组第0位是gcd还是x了。如果项目用的是BigInteger我建议只在跨API边界时使用。因为BigInteger虽然安全但性能比原生long差一个量级而且不可变对象在循环里频繁创建会给GC造成压力。数论算法核心计算用long快速算出结果最后需要对外暴露时才转成BigInteger这是性能和安全的平衡点也是我在生产环境里调优时最常做的一件事。