给定两个整数 a 和 b。

求最大公约数的办法可以使用辗转相除法，时间复杂度是 O(logn)，n 是 max(a,b)。

求最小公倍数的方法是利用 GCD：将两数相乘再除以 GCD。这里要注意防止溢出，可以使用其中一个数 a 先除以 GCD 再乘以另一个数 b。

最大公约数 GCD: 辗转相除法

GCD（除数，被除数） = GCD（余数，除数），核心就是将余数变成新的除数，最后返回被除数。

1
2
3
4
5
6
7
8
9
10
11
12

private int gcd(int a, int b) {
    // a 是除数，b 是被除数
    while (a != 0) {
        int tmp = a;  // 记录除数
        a = b % a;  // 余数成为新的除数
        b = tmp;  // 除数成为新的被除数
    }
    // 当余数为 0 时，说明 被除数 和 除数 之间是倍数关系，直接返回被除数
    return b;  
}

最小公倍数 LCM

想求 LCM，必须先求 GCD。

1
2
3
4
5
6
7
8
9
10
11
12
private int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

private int gcd(int a, int b) {
    while (a != 0) {
        int tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}