求两个正整数a,b的最大公约数。java使用欧几里得算法

欧几里得算法，也称辗转相除法，是求最大公约数的一种方法。其基本思想是用较大的数除以较小的数，然后用较小的数去除余数，如此反复，直到余数为零为止。

Java代码实现如下：

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

其中，gcd方法接受两个参数a和b，返回它们的最大公约数。如果b为零，则a即为最大公约数；否则，递归调用gcd方法，传入参数b和a%b（即a除以b的余数），直到b为零为止。

相关问题

求两个正整数a,b的最大公约数。使用欧几里得算法

欧几里得算法又称辗转相除法，是一种求最大公约数的算法。

算法步骤如下：

1. 对于两个正整数a,b，假设a>b，求a÷b得商q和余数r，即a=bq+r，其中r为a÷b的余数。

2. 如果r=0，说明b就是最大公约数，结束算法。

3. 如果r≠0，用b代替a，用r代替b，即a=r，b=r÷q的余数，然后继续执行步骤1。

根据以上算法，可以编写如下的Python代码实现求两个正整数a,b的最大公约数：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

其中，a, b = b, a % b这一行代码实现的是将b赋值给a，将a÷b的余数赋值给b，相当于执行了上述的步骤3。最终返回a即为最大公约数。

用Java的方法求欧几里得算法是用来求两个正整数最大公约数的算法。欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。 假如：需要求 1997 和 615 两个正整数的最大公约数，使用欧几里得算法是这样进行的： 1997 / 615 = 3 （余 152） 615 / 152 = 4（余7） 152 / 7 = 21（余5） 7 / 5 = 1（余2） 5 / 2 = 2 （余1） 2 / 1 = 2 （余0） 至此，最大公约数为1。 点击复制后，将打开C知道体验页

答案：可以使用以下Java代码实现欧几里得算法：

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

使用上述代码，可以通过调用gcd(1997, 615)方法来求得1997和615的最大公约数，结果为1。