java 求两个整数的最大公约数

求两个整数的最大公约数（Greatest Common Divisor, GCD），通常可以使用欧几里得算法（Euclidean Algorithm）。这个算法基于数学原理：两个整数a和b（假设a >= b）的最大公约数等于a除以b的余数c与b之间的最大公约数。如果c为0，则b就是原两数的最大公约数；否则，继续用b除以c，直到余数为0。

以下是使用Java语言实现欧几里得算法的一个简单版本：

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

    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;
        System.out.println("The greatest common divisor of " + num1 + " and " + num2 + " is " + gcd(num1, num2));
    }
}

在这个例子中，`gcd`函数递归地计算两个数的最大公约数。当你运行这段程序，它会返回48和18的最大公约数6。

相关问题

Java求两个整数最大公约数，递归法

在Java中，我们可以使用欧几里得算法（也称为辗转相除法）来递归地计算两个整数的最大公约数（GCD）。这个算法基于这样一个事实：对于任意两个正整数a和b，它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

以下是递归求解GCD的Java代码：

public class Main {
    public static int gcd(int a, int b) {
        // 如果b为0，则a就是最大公约数
        if (b == 0) {
            return a;
        } else {
            // 递归调用gcd函数，将b和a除以b的余数作为新的a和b
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args) {
        int num1 = 48, num2 = 18;
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd(num1, num2));
    }
}

在这个例子中，`gcd(a, b)` 函数会一直调用自身，直到 `b` 变成0为止。当 `b` 为0时，`a` 就是最大公约数。如果需要输入用户自定义的数字，可以在 `main` 函数中修改 `num1` 和 `num2` 的值。

java求两个正整数最大公约数

可以使用欧几里得算法（辗转相除法）求解。具体步骤是：将两个数中较大的数除以较小的数，记作q1余r1，然后用较小的数除以r1，得到q2余r2，以此类推，直到余数为0为止。此时，最大公约数即为最后一个非零余数。