f 求解最小公倍数和最大公约数是很常见的算法题。比较普遍的求解最大公约数使用的是欧几里得算法（辗转相除法），而最小公倍数可以在最大公约数的基础上求得。

最大公约数

欧几里得算法的数学实质是:
$gcd(a,b)=gcd(a,a\mod b)$

这里的 $gcd$ 是最大公约数的英文缩写, mod 是求余的意思

其的算法步骤为:

1. 输入两个正整数a, b
2. 计算 a % b = r
3. 互换:a = b, b = r
4. 如果 r = 0,此时 a 就是最大公约数，否则继续第 2 步
   如此用 c 语言实现如下:

1
2
3
4
5
6
7
8

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

最小公倍数

对于两个数有:
$a \times b = gcd(a,b)\times lcd(a,b)$
所以可得最小公倍数为:
$lcd(a,b)=a\times b\div gcd(a,b)$
显然我们已经得到了最大公倍数，接下来只需要带入即可，具体代码如下:

1
2
3
4

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