Noob
0%

最大公约数与最小公倍数

发表于 更新于 分类于 ，

最大公约数

思路：使用欧几里得算法（辗转相除法），循环取除数和余数，直到余数为零。

1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
    int tmp = 0;
    while(b != 0 ) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

最小公倍数

思路： 两数的最小公倍数等于两数的积与两数的最大公约数的商

1
2
3
int lcd(int a, int b) {
    return (a * b) / gcd(a, b);
}