1. 概述
给定两个整数 a 和 b，如果它们的最大公约数为 1，我们就称它们是 互质（relatively prime） 的。有时也被称为 互素 或 coprime。
在本篇教程中，我们将通过 Java 来实现如何判断两个数是否互质。
2. 最大公约数算法
判断两个数是否互质，核心在于求它们的最大公约数（gcd）。如果 gcd(a, b) = 1，那么 a 和 b 就是互质的。
因此，我们的问题转化为：如何高效地计算两个数的最大公约数。
3. 欧几里得算法实现
我们使用经典的 欧几里得算法（Euclidean Algorithm） 来计算两个整数的最大公约数。
该算法的核心思想是：
- 用较大的数除以较小的数，得到余数；
- 将较小的数作为新的被除数，余数作为新的除数；
- 重复上述步骤，直到余数为 0；
- 此时的除数就是最大公约数。
举个例子，我们来计算 a = 81 和 b = 35 的最大公约数：
81 ÷ 35 = 2 余 11
35 ÷ 11 = 3 余 2
11 ÷ 2 = 5 余 1
2 ÷ 1 = 2 余 0
最终余数为 0，此时除数为 1，说明 gcd(81, 35) = 1，因此它们互质 ✅。
3.1 迭代实现
下面是一个使用迭代方式实现的 Java 版本：
int iterativeGCD(int a, int b) {
int tmp;
while (b != 0) {
if (a < b) {
tmp = a;
a = b;
b = tmp;
}
tmp = b;
b = a % b;
a = tmp;
}
return a;
}
这段代码通过不断交换 a 和 b 的值，模拟了欧几里得算法的计算过程。
3.2 递归实现
如果你更喜欢函数式风格，也可以使用递归实现：
int recursiveGCD(int a, int b) {
if (b == 0) {
return a;
}
if (a < b) {
return recursiveGCD(b, a);
}
return recursiveGCD(b, a % b);
}
这个版本逻辑更清晰，也更简洁，适合理解算法流程。
4. 使用 BigInteger 的 gcd 方法
其实，Java 已经为我们提供了现成的 gcd 实现：BigInteger.gcd() 方法。它内部也是基于欧几里得算法实现的。
我们可以借助它，非常简单地实现判断两个数是否互质：
boolean bigIntegerRelativelyPrime(int a, int b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE);
}
✅ 优点：代码简洁、可读性强
❌ 缺点：需要将 int 转换为 BigInteger，在性能敏感场景下略显笨重
5. 总结
本篇教程中，我们介绍了三种判断两个整数是否互质的方式：
- 迭代实现欧几里得算法：适合性能敏感场景
- 递归实现欧几里得算法：适合教学或理解算法逻辑
- **使用
BigInteger.gcd()**：简单、安全，适合日常开发使用
你可以根据实际需求选择合适的实现方式。比如在算法题中，建议自己实现 gcd；在业务代码中，直接使用 BigInteger 更省事。
如需查看完整示例代码，欢迎访问 GitHub 仓库。