最大公约数和最小公倍数

最大公约数（gcd）

1. 辗转相除法

用较大数除以较小数，再用出现过的余数除以更小的数，直到余数为0为止。那个被除数就是我们要找的最大公约数。

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

最小公倍数（lcm）

1. 辗转相除法

最小公倍数 = (a * b) / 最大公约数

public static long lcm(long a, long b) {
    return a * b / gcd(a, b);
}