Java面试必备数论算法：GCD、素数筛与快速幂全解析

1. 为什么Java开发者绕不开数论这道坎1.1 从面试高频题看数论的具体考点我这两年帮人做面试辅导和简历复盘发现一个很有意思的现象Java后端岗位的算法面试里数论题出现的频率远比大多数人想象的高。很多人以为数论是ACM竞赛的专利结果一刷LeetCode碰到“统计质数”“字符串相乘”“最大公约数”“Pow(x, n)”这类题目就卡壳。原因倒不是题目本身多难而是学校的数据结构课几乎没有把数论当成一个正经章节来讲大家脑子里只有数组、链表、树、图一看到和“数学”沾边的问题就开始慌。实际上Java面试里的数论题有非常明确的考法几乎集中在四个点最大公约数GCD与扩展欧几里得、素数判定与筛法、快速幂与模运算、质因数分解。它们很少单独出现通常嵌套在数组处理、字符串处理、动态规划的题目里作为中间步骤出现。比如“给定一个整数数组返回所有数对的最大公约数之和”这类题的核心就是GCD算法本身够不够熟再比如“计算大数组合数对某个质数取模”核心其实是乘法逆元和快速幂。从数据结构与算法的整体知识结构来看数论属于典型的“算法思维放大器”。也就是说它不直接教你链表怎么反转、二叉树怎么遍历但它给了你一套处理整数问题的底层工具。你掌握了这套工具之后很多原本看不懂的题解瞬间就能串起来了。这也是为什么我在任何一份Java学习路线里都会建议把数论当作和排序、二分、动态规划并列的一个独立专题来学。1.2 招聘市场上数论能力被低估了还有一个现实因素值得说八股文能背算法题能刷但数论题是最难“背答案”的一类题。因为它的变式太多一个考点可以从GCD衍生出裴蜀定理、线性丢番图方程、模逆元求解等问题。面试官出一道理数论题主要就是想考察两件事第一候选人有没有体系化的算法知识储备还是只会背模板第二候选人面对陌生数学问题时能不能冷静地把问题拆解成已知模型。我之前带过一个小伙伴Java基础很扎实集合源码、并发包、JVM调优都能聊结果面某大厂时碰到一道“统计[L,R]区间内所有质数的个数”的题。他知道用埃氏筛但因为平时没写过手撕的时候边界处理错了数组越界当场就慌了。后来他回去花了三周把数论专题系统补了一遍再面其他公司的时候同类型题目直接秒杀。这个例子我经常拿来跟身边的人说数据结构与算法不能只围着“结构”转数学工具这块短板一定要补齐尤其是用Java写的时候还涉及溢出、类型转换这些容易被忽略的工程细节。这篇文章我就围绕Java里最常用到的几类数论算法把原理、模板代码、复杂度分析、实际踩坑经验一次讲清楚。你如果正在准备Java面试或者工作中需要处理大整数计算、哈希、加密相关逻辑这篇文章应该能帮你少走不少弯路。2. 最大公约数从辗转相除法到扩展欧几里得2.1 三种实现GCD的方式复杂度差异比想象中大求最大公约数是整个数论算法的基础因为很多高阶算法比如模逆元、分数约分、裴蜀定理都建立在GCD之上。最经典的实现就是辗转相除法也叫欧几里得算法核心原理是一条恒等式gcd(a, b) gcd(b, a % b)这条恒等式的正确性依赖一个事实a和b的公因数集合等于b和(a % b)的公因数集合。你用例子去推很快就能理解gcd(48, 18) gcd(18, 12) gcd(12, 6) gcd(6, 0) 6。我在实际工程里最常用的就是递归写法public static int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }这段代码有几个容易被忽略的细节。第一参数顺序不需要特意保证a b因为递归第一次调用就会自动交换顺序第二递归深度非常有限最坏情况下也不会超过O(log min(a,b))所以完全不用担心栈溢出第三Java里%运算符对负数的结果符号和数学定义不一样后面我会专门讲坑。还有一种更稳定的写法是while循环避免递归过程中栈帧的重复创建public static int gcd(int a, int b) { while (b ! 0) { int tmp a % b; a b; b tmp; } return a; }这种写法在性能敏感的场景下会比递归快一点因为省去了方法调用的开销。不过说实话现代JVM的方法内联优化很成熟这个差异在绝大多数场景下可以忽略。真正选择迭代而不是递归的理由更多是个人代码风格偏好。还有一个更暴力的实现是Stein算法它通过位运算避免取模运算适合在超大规模整数场景下使用。但在Java的int和long范围内取模运算的开销完全在可接受范围内所以实际工程里我还是推荐用欧几里得算法代码简洁逻辑清晰面试时也好解释。2.2 扩展欧几里得不止能求GCD还能求乘法逆元如果面试官在GCD的基础上继续追问下一个考点几乎必然是扩展欧几里得算法。它解决的是一类更复杂的问题给定整数a和b求整数x和y使得ax by gcd(a, b)这个等式被称为贝祖等式x和y一定存在这就是裴蜀定理。它的实际用途太广了最典型的就是求模逆元。什么是模逆元如果存在整数x使得 (a * x) % m 1那么x就叫做a在模m意义下的逆元。模逆元在组合数取模、RSA加密、哈希函数设计里都有应用。比如要计算分数 (a / b) 对一个大质数取模直接做除法是不可能的必须先把b的逆元算出来然后用乘法代替除法。扩展欧几里得算法在Java里的经典实现大概是这个样子的public static long[] exgcd(long a, long b) { if (b 0) { return new long[]{a, 1, 0}; } long[] vals exgcd(b, a % b); long gcd vals[0]; long x vals[2]; long y vals[1] - (a / b) * vals[2]; return new long[]{gcd, x, y}; }注意返回值我封装成了一个long数组第一个元素是gcd第二个是x第三个是y。这里最关键的一行是y vals[1] - (a / b) * vals[2]它本质上是利用了递归回代的过程。如果你第一次接触这个算法建议拿具体数字手推一两遍光看代码很容易绕晕。有了exgcd求逆元就很简单了。前提是a和m互质否则逆元不存在public static long modInverse(long a, long m) { long[] vals exgcd(a, m); long gcd vals[0]; if (gcd ! 1) { throw new ArithmeticException(逆元不存在: gcd(a, m) ! 1); } long x vals[1]; return (x % m m) % m; }很多人在最后一步容易犯迷糊为什么算出来的x还要模m因为exgcd求出的x可能是一个负数也可能是某个超大值但在模m意义下它只需要落在[0, m-1]区间内所以要先取模再加m再取模保证结果非负。这个操作我在面试里看很多人直接返回x结果错了还一脸懵。2.3 Java负数取模的坑Math.floorMod可能是你的救星说到取模必须单独拿出来讲一个Java特意挖的坑%运算符对负数结果的符号和数学上不一样。数学意义上的模运算结果永远是0到模数减1之间的非负整数。但Java的%遵循的是“被除数的符号”也就是说-7 % 3的结果是-1而不是2。很多初学者在这里踩坑尤其在做环形数组、循环队列、哈希散列这类需要保证下标非负的场景%直接甩负数出来数组越界异常就跟着来了。int index hash % length; // 如果hash是负数index可能是负数在数论算法的实现中这个问题更隐蔽。比如前面计算模逆元你明明求出了正确的x结果因为%的符号问题最后返回了一个负数。我见过不止一个同事在这种地方排查了很久最后发现是Java取模符号的锅。解决办法有两种。第一种是手动调整int result ((a % m) m) % m;第二种是直接用Java 8引入的Math.floorModint result Math.floorMod(a, m);Math.floorMod的语义是返回不大于a / m的商对应的余数结果一定和被除数同号于除数最终保证结果在[0, m-1]区间内。实际工作中我推荐凡是涉及数论取模、数组下标计算的地方统一用Math.floorMod或者“先模再加再模”的写法不要心存侥幸。3. 素数判定与筛法面试常客背后的复杂度直觉3.1 朴素判定为什么不行从时间复杂度说起素数判定是数论专题里最“亲民”的内容小学就学过质数的定义。但面试里问素数问题从来不是让你按定义暴力遍历而是要你在足够大的数据范围下给出高效方案。先看最朴素的写法public static boolean isPrime(int n) { if (n 1) { return false; } for (int i 2; i n; i) { if (n % i 0) { return false; } } return true; }时间复杂度O(n)。对单个小整数没问题但如果你要判断100万个数字是不是质数O(n)乘以100万就是10的12次方量级的操作直接超时。稍微优化一点的写法是把循环条件改成i * i npublic static boolean isPrime(int n) { if (n 1) { return false; } if (n 2) { return true; } if ((n 1) 0) { return false; } for (int i 3; i * i n; i 2) { if (n % i 0) { return false; } } return true; }这里用到了两个优化一是合数n一定有一个不大于根号n的因子所以循环到i * i n就够了二是提前排除偶数让循环步长为2直接把计算量砍半。判断单个数字时这个版本的性能已经很好了时间复杂度降到O(√n)。我在实际教学中反复强调一个原则用朴素判定之前先估算数据规模。如果单个数字不超过10^12的量级用优化后的试除法完全够用如果是一次性判定大量数字就必须上筛法了。3.2 埃氏筛和线性筛两种筛法的实现差异面试里“统计小于n的质数个数”几乎是必考题LeetCode第204题就是。70万以下的n用埃氏筛就可以高效搞定较大规模则推荐线性筛。埃氏筛的思路特别直观从2开始把每个质数的倍数全部标记为合数。比如2是质数那就把4、6、8、10……全部标记下一个未标记的是3那就把9、12、15……全部标记。最终没被标记的就是质数。public static int countPrimes(int n) { if (n 2) { return 0; } boolean[] isComposite new boolean[n]; int count 0; for (int i 2; i n; i) { if (!isComposite[i]) { count; if ((long) i * i n) { for (int j i * i; j n; j i) { isComposite[j] true; } } } } return count; }这里有个细节值得注意内层循环从i * i开始而不是2 * i。因为比i * i小的合数早就被更小的质数标记过了从i * i开始可以避免大量重复标记。这个优化能让埃氏筛的时间复杂度达到O(n log log n)已经非常接近线性了。但埃氏筛有一个小问题同一个合数可能被多个质数重复标记。比如30会被2、3、5各标记一次。数据规模一大重复标记带来的多余操作仍然可感知。于是就有了线性筛欧拉筛它保证每个合数只被它的最小质因子标记一次让时间复杂度严格达到O(n)。public static int countPrimesLinear(int n) { if (n 2) { return 0; } boolean[] isComposite new boolean[n]; int[] primes new int[n]; int primeCount 0; for (int i 2; i n; i) { if (!isComposite[i]) { primes[primeCount] i; } for (int j 0; j primeCount (long) i * primes[j] n; j) { isComposite[i * primes[j]] true; if (i % primes[j] 0) { break; } } } return primeCount; }线性筛的核心在于那句if (i % primes[j] 0) break;。它的作用是保证每个合数只被“最小质因子 × 某个数”的组合筛掉。如果i能被primes[j]整除说明primes[j]已经是i的最小质因子再往后乘以更大的质数得到的结果的最小质因子仍然是primes[j]但那个结果会在后续被别的方式处理现在标记只会重复。这个算法我在面试时经常让人手写大多数人第一次都写不对那个break条件。建议你自己动手跑一遍6到30的过程观察每个合数是被谁标记的理解会深刻很多。3.3 为什么工程上有时还得用区间筛面试里还可能出现一类变种题统计一个超大区间[L, R]内的质数数量比如L10^9R10^9100000。这个范围如果直接开数组内存直接爆炸。标准解法是区间筛先用普通筛法求出[2, √R]范围内的所有质数然后用这些质数去标记[L, R]范围内的合数。因为任何一个合数n都一定有一个不大于√n的质因子所以用[2, √R]的质数去筛[L, R]一定能筛掉所有合数。public static ListInteger sieveInRange(long L, long R) { int limit (int) Math.sqrt(R) 1; boolean[] isPrimeSmall simpleSieve(limit); boolean[] isComposite new boolean[(int) (R - L 1)]; for (int i 2; i limit; i) { if (isPrimeSmall[i]) { long start Math.max((long) i * i, ((L i - 1) / i) * i); for (long j start; j R; j i) { isComposite[(int) (j - L)] true; } } } ListInteger result new ArrayList(); for (int i 0; i isComposite.length; i) { if (!isComposite[i] L i 2) { result.add((int) (L i)); } } return result; }这里的((L i - 1) / i) * i是向上取整到i的最小倍数确保从大于等于L的位置开始标记避免把区间外的小数字也算了进来。区间筛在工程上的典型应用场景是大数分解前置处理面试时遇到基本属于加分题。4. 快速幂与模运算大数幂取模的工程价值4.1 从循环乘法到二进制分解快速幂解决的问题很直接计算a的b次方尤其是对结果取模。如果直接循环乘b次时间复杂度O(b)b一大就超时。快速幂的核心思想是把指数b按二进制拆解利用a^(2^k)可以由a^(2^(k-1))平方得到这一性质把复杂度降到O(log b)。举个例子计算3^13。13的二进制是1101所以3^13 3^(841) 3^8 * 3^4 * 3^1只需要不断把底数平方然后根据当前二进制位是否为1决定是否累乘到结果里。代码实现非常简洁public static long fastPow(long a, long b, long mod) { long result 1 % mod; a a % mod; while (b 0) { if ((b 1) 1) { result result * a % mod; } a a * a % mod; b 1; } return result; }注意第一步result 1 % mod这不是多余的。如果mod为1任何数对1取模都是0直接初始化成1会导致错误结果。虽然后续代码在mod1时会因为取模变成0但为了严谨仍然建议这样写。这种边界情况在面试中不一定会测但在工程代码里可能真的会遇到。4.2 Java溢出陷阱为什么取模还会爆long这里必须讲一个Java程序员最容易踩的坑result * a % mod这一步result * a先执行的是一个普通的long乘法可能还没等取模就溢出了。假设mod取10^97这个常见质数result和a都可能是接近mod的数值两者相乘大约是10^18量级long的最大值是9.22×10^18看起来没问题。但如果mod取10^10两个接近mod的数相乘就是10^20直接爆long。实际开发中我见过不止一次的线上问题加密签名模块里用了快速幂模数上了10^12之后计算结果随机出错排查半天发现是乘法溢出。解决思路有几个使用BigInteger的multiply方法安全但慢使用Java 8的Math.multiplyExact在溢出时抛异常用来兜底使用java.math.BigInteger.modPow直接算模幂工程上最省心自己实现“按位乘加”模拟大整数乘法算法竞赛常用但工程里不必。我个人的建议是面试手撕代码用long 取模完全够用因为题目给的mod基本都会控制在10^97或10^99这种安全范围生产环境涉及大模数直接用BigInteger.modPow别自己造轮子。造轮子一时爽溢出火葬场。4.3 快速幂的典型应用组合数取模与降幂公式快速幂最常见的一个应用场景是组合数取模也就是计算C(n, k) % p其中p是质数。当n和k特别大的时候直接用公式阶乘相除是行不通的因为中间结果即使使用long也会溢出。标准方案是通过预处理阶乘和逆元来完成public class Combination { private final long mod; private final long[] fact; private final long[] invFact; public Combination(int maxN, long mod) { this.mod mod; fact new long[maxN 1]; invFact new long[maxN 1]; fact[0] 1; for (int i 1; i maxN; i) { fact[i] fact[i - 1] * i % mod; } invFact[maxN] modInverse(fact[maxN], mod); for (int i maxN - 1; i 0; i--) { invFact[i] invFact[i 1] * (i 1) % mod; } } public long combine(int n, int k) { if (k 0 || k n) { return 0; } return fact[n] * invFact[k] % mod * invFact[n - k] % mod; } }这段代码里用到了一个技巧先算出n!的逆元然后倒着推出所有阶乘的逆元。因为invFact[i] invFact[i1] * (i1) % mod这样就不需要为每个阶乘都调用一次求逆元的函数预处理的整体复杂度从O(n log mod)降到了O(n)。还有一类题目会考幂的降幂公式比如需要计算a^b % m但b不是普通整数而是类似于“一个非常大的数比如10^100000”时你需要用欧拉定理或费马小定理把指数降下来。这部分又牵扯到欧拉函数面试中出现频率相对低一些但大厂压轴题偶尔会考建议有精力的时候把扩展欧拉定理也一起看了。5. 数论代码在Java里的工程规范与测试方法5.1 数据类型选择三原则数论算法对数据类型极其敏感同样的代码int、long、BigInteger跑出的结果天壤之别。我总结了三条规定基本能覆盖绝大多数场景。第一条能算清楚范围就用long别偷懒用int。即使题目给的输入范围看起来不大乘积中间值也可能超出int。典型例子是求GCD时中间过程不涉及乘法还好一旦用到扩展欧几里得的回代公式y vals[1] - (a / b) * vals[2]这里的乘法就可能导致int溢出。我的经验是数论算法的运算变量一律声明为long除非你能明确证明所有中间值都在int范围内。第二条模数超过10^9时乘法要先检查溢出风险。快速幂等算法中两个小于mod的值相乘可能超过long的范围。如果mod本身超过10^9建议直接考虑BigInteger或者在乘法之前判断并用Math.multiplyExact捕获溢出。第三条需要精确大整数结果时直接用BigInteger不要强行用long硬扛。BigInteger虽然慢但Java工程讲究可靠优先。尤其是加密、签名、哈希这类安全敏感型代码强行用原始类型导致Bug的代价远比性能损失高。5.2 数论代码的测试边界值优先数论代码的Bug大多藏在边界条件里。我之前总结了一套针对数论算法的测试清单分享给大家输入0、1、负数、Integer.MAX_VALUE、Long.MAX_VALUE待判定数字是质数如2、3、97、合数如1、49、100、大质数GCD参数中一个为0的情况比如gcd(0, 5)应该返回5模逆元中a和m互质与不互质两种情况快速幂中指数b为0、底数a为0或1、模mod为1的情况组合数中k0、kn、kn的情况。针对这些边界你可以在本地写一个简单的main方法把结果打印出来逐一核对。更专业的做法是写JUnit参数化测试把这些边界值全部变成测试用例。Test public void testGcdBoundary() { assertEquals(5, gcd(0, 5)); assertEquals(5, gcd(5, 0)); assertEquals(1, gcd(1, 1)); assertEquals(6, gcd(48, 18)); assertEquals(1, gcd(Integer.MAX_VALUE, 2)); }这套习惯看起来琐碎但非常救命。我遇到过两次“算法本身写对了但被边界值卡住”的情况一次是gcd(0, 5)返回了0一次是快速幂在mod1时返回了1而不是0。这些问题面试中不会每次都测但在生产代码里一旦出现就是事故。5.3 在面试中遇到数论题先别急着写代码讲了这么多算法最后补一个实战技巧面试遇到数论题先在草稿纸上花两分钟确认问题模型再动手写。很多候选人拿到“计算x的n次方对m取模”这类问题第一反应就是写一个for循环乘到底然后和面试官讨论超时问题。这其实暴露的是建模能力弱。正确的做法是先把输入范围圈出来判断朴素解法是否可行再用快速幂、矩阵快速幂或BigInteger.modPow去解决。还有一个容易被忽略的细节在面试中主动说出你的复杂度分析。比如写了线性筛要能说出为什么它是O(n)而不是O(n log log n)写了扩展欧几里得要能解释为什么它能求出贝祖等式的解。这个过程比代码本身更能体现数据结构与算法功底。面试官愿意出数论题就是想听到这个层面的东西。6. 数论题在LeetCode场景中的归约实战6.1 判定类题目识别“质数模型”LeetCode第204题“计数质数”就是最典型的判定类数论题它要求统计小于n的所有质数个数。这道题的陷阱在于n的取值范围可以达到5×10^6朴素判定必然超时需要用筛法。你可以直接用前面给的埃氏筛模板注意边界条件n小于等于2的时候直接返回0因为小于2的范围内没有质数。还有一类和质数判定相关的变种题是把一个数字拆成若干个质数的和。这种题表面上是动态规划实际上也要先用筛法把所有质数准备好再用一个一维DP数组去凑。你会发现数论在这里是前置步骤核心解法还是动态规划但少了质数表这道工序整个题就没法做。6.2 计数类题目组合数与逆元结合LeetCode上有一类“计算组合数对10^97取模”的题目比如统计路径数、方案数。这类题选手直接套公式是不行的因为阶乘和阶乘的除法在取模意义下都不能直接做。正确流程是先预处理阶乘数组和逆元数组然后用fact[n] * invFact[k] * invFact[n-k] % mod得到结果。如果n特别大超过10^7预处理阶乘的O(n)方案也扛不住这时要用Lucas定理把n和k按质数p的进制拆开逐位计算组合数。Java实现Lucas定理时要注意递归深度和long溢出我一般会把p比较小的情况单独处理避免不必要的性能损耗。6.3 模拟类题目循环节与周期性还有一类不太容易联想到数论的题目实际考的是模运算的周期性。比如“计算1^1 2^2 3^3 ... n^n的最后k位数字”这类题的数字增长速度极快直接算肯定溢出。解法是利用模运算的循环节性质找到幂次和底数的周期把n折小后再计算。这类题型的核心要领是先确定模数再通过快速幂计算每一项取模后的值最后汇总取模。如果n特别大还需要分析是否存在循环节。比如底数按模m循环指数按phi(m)循环两者结合之后一般能找到总周期从而实现O(周期长度)的计算。这个技巧在无锁哈希和一致性哈希的底层实现里也有应用属于找工作时的隐形加分项。把前面这些模型识别清楚大部分数论题目就不再是“数学题”而是一眼能看穿题面的套路题。数据结构与算法这个学科本来就是靠“识别问题模型 调用对应工具”来解决问题的数论只是其中一组相对独立但非常重要的工具。