Java 中求最大公约数的几种方法

1. 概述

在数学中，最大公约数（GCD） 是指两个非零整数都能被整除的最大正整数。

在本文中，我们将介绍三种查找两个整数最大公约数（GCD）的方法，并给出其 Java 实现。

这些方法在算法复杂度和实现难度上各有不同，适用于不同的场景。如果你在实际开发中遇到需要频繁计算 GCD 的场景，或者想了解底层原理，这篇文章应该能帮你理清思路。

---

2. 暴力法（Brute Force）

这是最直观的方法：我们从 1 遍历到两个数中较小的那个，每次检查当前数字是否能同时整除这两个数，最后记录下最大的那个能整除两数的值。

✅ 优点：逻辑简单，容易理解
❌ 缺点：效率较低，时间复杂度高

示例代码如下：

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

时间复杂度分析：

该方法的时间复杂度为 O(min(n1, n2))，因为我们需要遍历到较小的那个数为止。

⚠️ 踩坑提醒： 当输入的两个数非常大时，这种方法效率会非常低，不推荐用于性能敏感的场景。

---

3. 欧几里得算法（Euclid’s Algorithm）

欧几里得算法是一种经典的、高效的 GCD 计算方法，其核心思想基于以下两个定理：

1. 如果 a > b，那么 gcd(a, b) = gcd(b, a % b)
2. 当 b == 0 时，a 就是最大公约数

✅ 优点：实现简单，效率高
❌ 缺点：递归实现可能会导致栈溢出（极端情况下）

示例代码如下：

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

时间复杂度分析：

该算法的时间复杂度为 O(log min(n1, n2))，比暴力法快很多，是实际中最常用的方法之一。

---

4. 斯坦因算法（Stein’s Algorithm）或称二进制 GCD 算法

斯坦因算法是一种利用位运算来替代除法运算的 GCD 算法。它适用于大整数的 GCD 计算，特别是在硬件不支持除法运算的平台上。

该算法利用了如下几个基本恒等式：

1. gcd(0, 0) = 0, gcd(n1, 0) = n1, gcd(0, n2) = n2
2. 若 n1 和 n2 都是偶数，则 gcd(n1, n2) = 2 * gcd(n1/2, n2/2)
3. 若 n1 是偶数，n2 是奇数，则 gcd(n1, n2) = gcd(n1/2, n2)
4. 若 n1 和 n2 都是奇数，且 n1 >= n2，则 gcd(n1, n2) = gcd((n1-n2)/2, n2)

✅ 优点：适用于大整数，避免除法运算
❌ 缺点：实现略复杂，代码可读性较差

示例代码如下：

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

时间复杂度分析：

• 当 n1 > n2 时，时间复杂度为 O((log2 n1)^2)
• 当 n1 < n2 时，时间复杂度为 O((log2 n2)^2)

⚠️ 说明： 由于该算法主要使用位运算，适合处理大整数或嵌入式系统中除法效率低的环境。

---

5. 总结

本文介绍了三种在 Java 中计算两个整数最大公约数（GCD）的方法：

方法	时间复杂度	是否推荐	适用场景
暴力法	O(min(n1, n2))	❌	简单理解，不推荐实战
欧几里得算法	O(log min(n1, n2))	✅	最常用，性能好
斯坦因算法	O((log n)^2)	✅（特定场景）	大整数或无除法支持平台

如果你在实际开发中需要频繁计算 GCD，建议优先使用 欧几里得算法，实现简单、效率高，是最优选择。

完整示例代码已上传至 GitHub（示例地址：github.com/yourname/gcd-example），欢迎 star 和 fork。