Java函数如何实现求最大公约数

在 Java 中，可以使用欧几里得算法或更相减损术实现求最大公约数。

欧几里得算法，也称辗转相除法，用于求两个整数的最大公约数。其基本思想是：

1. 如果 a 能够整除 b，那么 a 就是最大公约数；

2. 否则，将 a 对 b 取余，得到余数 c，再用 b 对 c 取余，继续得到余数 d，一直循环直到余数为 0，此时前一个非零余数即为最大公约数。

实现思路如下：

public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

该函数实现了求 a 和 b 的最大公约数，如果 b 等于 0，那么 a 就是最大公约数，否则将 b 和 a 对 b 取余的结果递归调用该函数，直到 b 等于 0。

使用更相减损术进行求解，其基本思想是：

1. 如果 a 和 b 都是偶数，那么 gcd(a, b) = 2 * gcd(a/2, b/2)；

2. 如果 a 是偶数，b 是奇数，那么 gcd(a, b) = gcd(a/2, b)；

3. 如果 b 是偶数，a 是奇数，那么 gcd(a, b) = gcd(a, b/2)；

4. 如果 a 和 b 都是奇数，那么 gcd(a, b) = gcd(|a-b|/2, min(a, b))。

实现代码如下：

public static int gcd(int a, int b) {
    if (a == b) {
        return a;
    }
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    if ((a & 1) == 0 && (b & 1) == 0) { // a 和 b 都是偶数
        return gcd(a >> 1, b >> 1) << 1;
    } else if ((a & 1) == 0) { // a 是偶数，b 是奇数
        return gcd(a >> 1, b);
    } else if ((b & 1) == 0) { // b 是偶数，a 是奇数
        return gcd(a, b >> 1);
    } else { // a 和 b 都是奇数
        return gcd(Math.abs(a - b) >> 1, Math.min(a, b));
    }
}

当 a 与 b 的值比较小时，欧几里得算法的效率更高，但当 a 与 b 的值接近时，更相减损术更具有优势。