如何求两个数的最大公约数

求几个整数的最大公约数大致有三种方法，求多个整数的最大公约数可以拆分为求两个整数的最大公约数，所以核心问题还是求两个整数的最大公约数。

穷举法

很直观就能想到穷举法，先找出两个数字中比较小的那一个min，然后逐个验证从2 ~ min的数字是否能被两个数整除，如果能同时被两个数字整除那就是公约数，找出其中最大的那个公约数就是所求的结果。

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

辗转相除法

辗转相除法是欧几里得想出来的，所以也叫做欧几里得算法。它的证明过程依赖于一个定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数，即gcd(a, b) = gcd(b, a mod b)，其中 gcd 表示最大公约数，此处假设 a > b。其证明过程如下所示：

设 c = gcd(a, b)；
则存在 m，n，使 a = mc，b = nc；
令 r = a mod b；
则存在 k，使 r = a - kb = mc - knc = (m - kn)c；
所以 gcd(b, a mod b) = gcd(b, r) = gcd(nc, (m-kn)c) = gcd(n, m-kn)c；
所以 c 为 b 与 a mod b 的公约数；

设 d = gcd(n, m-kn)；
则存在 x，y，使 n = xd，m-kn = yd；
所以 m = yd + kn = yd + kxd = (y + kx)d；
所以 a = mc = (y + kx)dc，b = nc = xdc；
所以 gcd(a, b) = gcd((y+kx)dc, xdc) = gcd(y+kx, x)dc = dc；
因为 gcd(a, b) = c，所以 d = 1；
即 gcd(n, m-kn) = 1，所以  gcd(b, a mod b) = c；
所以 gcd(a, b) = gcd(b, a mod b)；

证明 gcd(y+kx, x)dc = dc，即 gcd(y+kx, x) = 1：
前提条件：gcd(x, y) = 1；
假设 gcd(y+kx, x) != 1，则肯定 gcd(y+kx, x) > 1，设 gcd(y+kx, x) = i；
则 y+kx = ui，x = vi；
则 y = ui - kx = ui - kvi = (u-kv)i
则 gcd(x, y) = gcd(vi, (u-kv)i) = gcd(v, u-kv)i
因为 gcd(y+kx, x) = i > 1，gcd(v, u-kv) >= 1；
所以 gcd(x, y) > 1，与前提条件矛盾；
所以 gcd(y+kx, x) = 1

有了上面的基础之后，我们就可以总结出来一个算法实现的步骤了。设 r = a % b；如果 r 为 0 的话，那么 a 和 b 的最大公约数就是 b，否则就是求 b 和 a%b 的最大公约数。

// 递归写法
int gcd(int a, int b){
    // 用 b 来存储 a%b 的值
    if(b == 0){ 
        return a;
    }
    return gcd(b, a%b);
}

// 迭代写法
int gcd(int a, int b){
    while(b != 0){
        int t = b;
        a = t;
        b = a % b;
    }
    return a;
}

可以看到在算法实现过程中并没有先找出来最小的数字，这是因为程序会自动将最较大的那个数字放到 a 的位置，比如将gcd(75, 1000)带入我们的递归算法中则会变成gcd(1000, 75)。

辗转相减法

辗转相减法也叫更相减损术（尼考曼彻斯法），也是一种简便的求两个数的最大公约数的算法，它的特色是做一系列减法，从而求的最大公约数。比如两个自然数 36 和 27，用大数减去小数得 9 和 27，这时 9 小于 27，需要将两数交换即得 27 和 9，继续相减可得 18 和 9，然后 9 和 9，这时就可以得到两数的最大公约数为 9 了。其证明过程如下所示：

设 gcd(a, b) = x，a > b；
则有 a = mx，b = nx，m，n 均为正整数且 m > n；
c = a - b = mx - nx = (m - n)x；
因为 a 和 b 均为正整数，所以 c 也能被 x 整除；
所以 gcd(a, b) = gcd(b, a-b)

具体的算法实现步骤在第一段已经有一个比较清晰的例子了，这里可以直接给出实现代码。

// 递归写法
int gcd(int a, int b){
    if(a == b){
        return a;
    }
    return a > b ? gcd(a-b, b) : gcd(a, b-a);
}

// 迭代写法
int gcd(int a, int b){
    while(a != b){
        a > b ? a = a - b : b = b - a;
    }
    return a;
}

Guanngxu