使用Java函数如何实现计算两个整数的最大公因数？

最大公因数是指两个或多个数中最大的公约数，求最大公因数的方法有许多种，其中较常用的方法有质因数分解法、辗转相减法、辗转相除法等。而在 Java 中，可以通过递归函数实现求最大公因数的功能。

1. 质因数分解法

质因数分解法是通过分解数的质因数，然后求其公共因子得到最大公因数。该方法的实现步骤如下：

（1）将两个数分别分解成质因数的乘积。

（2）求出它们的公共因子，即出现在两个数的质因数中的公共因子。

（3）将这些公共因子乘起来，即得到最大公约数。

下面是实现代码：

// 质因数分解法求最大公因数
public static int getGCD(int num1, int num2) {
    List<Integer> primeFactors1 = getPrimeFactors(num1);
    List<Integer> primeFactors2 = getPrimeFactors(num2);
    List<Integer> commonFactors = new ArrayList<>();

    for (Integer factor : primeFactors1) {
        if (primeFactors2.contains(factor)) {
            commonFactors.add(factor);
            primeFactors2.remove(factor);
        }
    }

    int gcd = 1;
    for (Integer factor : commonFactors) {
        gcd *= factor;
    }
    return gcd;
}

// 获取一个数的质因数列表
private static List<Integer> getPrimeFactors(int num) {
    List<Integer> primeFactors = new ArrayList<>();
    for (int i = 2; i <= num / i; i++) {
        while (num % i == 0) {
            primeFactors.add(i);
            num /= i;
        }
    }
    if (num > 1) {
        primeFactors.add(num);
    }
    return primeFactors;
}

2. 辗转相减法

辗转相减法是通过反复相减，然后求其公共因子得到最大公因数。该方法的实现步骤如下：

（1）将两个数中较大的数减去较小的数，然后用得到的差再减去较小的数，反复操作，直到两数相等时停止。

（2）将停止时的两数的值作为最大公约数。

下面是实现代码：

// 辗转相减法求最大公因数
public static int getGCD(int num1, int num2) {
    if (num1 == num2) {
        return num1;
    } else if (num1 < num2) {
        return getGCD(num2 - num1, num1);
    } else {
        return getGCD(num1 - num2, num2);
    }
}

3. 辗转相除法

辗转相除法是通过反复取余数和整除，然后求其公共因子得到最大公因数。该方法的实现步骤如下：

（1）用两数中较大的数除以较小的数，得到余数。

（2）若余数为 0，则较小的数为最大公约数；

（3）否则，将较小的数用上一步的余数代替，然后重复 步，直到余数为 0，停止循环。

下面是实现代码：

// 辗转相除法求最大公因数
public static int getGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    } else {
        return getGCD(num2, num1 % num2);
    }
}