辗转相除法求最大公约数

辗转相除法是一种求最大公约数的简便方法。假设需要求两个整数 a 和 b 的最大公约数，步骤如下：

1. 用较小的数 b 除以较大的数 a，得到余数 r。

2. 如果 r 等于 0，则 a 就是最大公约数。

3. 如果 r 不等于 0，则用 b 除以 r，得到余数 r1。

4. 如果 r1 等于 0，则 r 就是最大公约数。

5. 如果 r1 不等于 0，则继续用 r 除以 r1，得到余数 r2。

6. 以此类推，直到得到余数为 0，此时最后一次的除数就是最大公约数。

例如，求 48 和 60 的最大公约数：

1. 用 48 除以 60，得到余数 48，记为 r。

2. 用 60 除以 48，得到余数 12，记为 r1。

3. 用 48 除以 12，得到余数 0，最后的除数 12 就是最大公约数。

因此，48 和 60 的最大公约数是 12。

相关问题

C++辗转相除法求最大公约数

C语言中，使用辗转相除法求最大公约数的方法有两种实现方式。一种是递归实现，另一种是循环实现。

递归实现的代码如下：

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

循环实现的代码如下：

int gcd(int a, int b) {
    if (b > a)
        return gcd(b, a);
    int remind = 1;
    while (remind) {
        remind = a % b;
        a = b;
        b = remind;
    }
    return a;
}

这两种方法的原理都是通过辗转相除的过程，即用较大的数除以较小的数得到余数，再用较小的数除以余数以此循环，直到最后余数为零。最后一次除的数即为最大公约数。

所以通过调用这两个方法，可以求出两个正整数的最大公约数。

java辗转相除法求最大公约数

在Java中，可以使用辗转相除法来求两个数的最大公约数。辗转相除法是一种求最大公约数的方法，也叫做欧几里德算法。具体的代码如下所示:

import java.util.Scanner;

public class GCD {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("请输入两个数：");
        int a = in.nextInt();
        int b = in.nextInt();

        while (b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }

        System.out.println("最大公约数是：" + a);
    }
}

以上代码通过辗转相除法，对输入的两个数进行取余操作。具体来说，就是用较大的数除以较小的数，如果余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，这时较小的数就是原来两个数的最大公约数。这个代码中使用了while循环，不断进行取余操作，直到余数为零。最后，输出的结果就是最大公约数。