最大公约数

两个数公共因数里最大的那个，叫最大公约数（GCD）。比如 12 的因数有 $1,2,3,4,6,12$，18 的有 $1,2,3,6,9,18$，公共的是 $1,2,3,6$，最大的是 6，所以 $\gcd (12,18)=6$。

最笨的办法是把两个数的因数都列出来找公共最大值，但没必要——下一节的辗转相除法几步就能算出。这里先看朴素理解：从两数中较小的往下试，第一个能同时整除两者的就是答案。

int gcdSlow(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;   // 循环结束时 g 是最大的公共因数
}

复杂度 $O(\min (a,b))$，数大就慢。常见坑：$\gcd$ 至少是 1（任何数都能被 1 整除），不会是 0；若其中一个数是 0，规定 $\gcd (a,0)=a$。真正考试要用的是下一节的高效算法。