AcWing 808. 最大公约数-欧几里得算法

输入两个整数 aa 和 bb，请你编写一个函数，int gcd(int a, int b), 计算并输出 aa 和 bb 的最大公约数。

输入格式

共一行，包含两个整数 aa 和 bb。

输出格式

共一行，包含一个整数，表示 aa 和 bb 的最大公约数。

数据范围

1≤a,b≤10001≤a,b≤1000

输入样例：

12 16

输出样例：

4

题解：

辗转相除法:
	又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。方法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。那么最后的除数就是这两个数的最大公约数。

例：求 123456 和 7890 的最大公因数。

图：辗转相除过程
答： 123456 和 7890 的最大公因数是 6

代码

import java.util.*;

public class Main {
    public static void main(String[] args)throws Exception {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        System.out.println(gcd(a, b));

    }

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