计算两非负整数最大公约数：辗转相除法（欧几里得算法）

计算两非负整数最小公倍数：通过这两个数的最大公约数间接求得

最大公约数

辗转相除法 (欧几里得算法, Euclidean algorithm)

依赖定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。即：

$$ \gcd(a,b)=\gcd(b,a\bmod b)\ (a>b,且r=a\bmod b,r\neq 0) $$

简单证明：

$a$ 可表示为 $a=kb+r$ $(r\neq0)$

假设 $\gcd(a,b)=d$，即 $d|a$ 且 $d|b$

$r=a-kb$，由 $d|a$ 且 $d|b$ 可知 $d|r$

由 $r<a$，$\gcd(a,b)=d$ 可知，$\gcd(b,r)=d$

综上，$\gcd(a,b)=\gcd(b,a\bmod b)$

复杂度

时间复杂度：$O(\log(a+b))$

（$a,b$ 为两个待计算的数字）

代码实现

int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

最小公倍数

我们知道：

$$ \operatorname{lcm}(a,b)=a\times b\div \gcd(a,b) $$

所以要求最小公倍数，我们直接用辗转相除法求出最大公约数，然后用上式即可。