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.floorMod：
int 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 <= n：
public 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]内的质数数量，比如L=10^9，R=10^9+100000。这个范围如果直接开数组，内存直接爆炸。
标准解法是区间筛：先用普通筛法求出[2, √R]范围内的所有质数，然后用这些质数去标记[L, R]范围内的合数。因为任何一个合数n，都一定有一个不大于√n的质因子，所以用[2, √R]的质数去筛[L, R]，一定能筛掉所有合数。
public static List<Integer> 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; } } } List<Integer> 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^(8+4+1) = 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会导致错误结果。虽然后续代码在mod=1时会因为取模变成0，但为了严谨，仍然建议这样写。这种边界情况在面试中不一定会测，但在工程代码里可能真的会遇到。
4.2 Java溢出陷阱：为什么取模还会爆long
这里必须讲一个Java程序员最容易踩的坑：result * a % mod这一步，result * a先执行的是一个普通的long乘法，可能还没等取模就溢出了。
假设mod取10^9+7这个常见质数，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^9+7或10^9+9这种安全范围；生产环境涉及大模数，直接用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[i+1] * (i+1) % 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的情况；
- 组合数中k=0、k=n、k>n的情况。
针对这些边界，你可以在本地写一个简单的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，一次是快速幂在mod=1时返回了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^9+7取模”的题目，比如统计路径数、方案数。这类题选手直接套公式是不行的，因为阶乘和阶乘的除法在取模意义下都不能直接做。正确流程是：先预处理阶乘数组和逆元数组，然后用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(周期长度)的计算。这个技巧在无锁哈希和一致性哈希的底层实现里也有应用，属于找工作时的隐形加分项。
把前面这些模型识别清楚，大部分数论题目就不再是“数学题”，而是一眼能看穿题面的套路题。数据结构与算法这个学科，本来就是靠“识别问题模型 + 调用对应工具”来解决问题的，数论只是其中一组相对独立但非常重要的工具。
