最大公约数

两个正整数的最大公约数（GCD，Greatest Common Divisor），是能同时整除它们的最大的数。比如 12 和 18，公约数有 1、2、3、6，最大的是 6，记作 $\gcd (12,18)=6$。

最直白的办法是从小到大试，把能同时整除两数的都记下来取最大：

int gcd(int a, int b) {
    int g = 1;
    for (int i = 1; i <= min(a, b); i++)
        if (a % i == 0 && b % i == 0) g = i;
    return g;
}

这样要循环到 $\min (a,b)$，复杂度 $O(\min (a,b))$，两数很大时会慢。

坑：约数一定不超过两数里较小的那个，所以循环上界取 $\min (a,b)$，别写成 $a\times b$ 白白多跑；还要注意 $a$ 或 $b$ 为 0 的特殊情况。下一节会学一个快得多的巧办法——辗转相除法，几乎瞬间出结果。