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

欧几里得算法，又称辗转相除法，是求最大公约数的一种方法。其基本思想是用较大的数去除较小的数，再用余数去除除数，如此反复，直到余数为零为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

Java代码实现：

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

其中，a和b为需要求最大公约数的两个正整数。如果b等于0，那么a就是最大公约数，直接返回a。否则，递归地调用gcd函数，将b和a除以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。