1. 辗转相除法

较大的数记为 a ，较小的数记为 b ，每次都执行 c = a % b ，然后令 a = b, b = c 。直至 b = 0 时， a 为最大公约数

算法模板

int gcd(int a, int b) {
    if(a < b) swap(a, b);
    while(b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

2. 枚举法

从大到小一个一个的试

3. 更相减损术

更相减损术出自《九章算术》，用来求解两个数的最大公约数
较大的记为 a ，较小的记为 b 。
其操作步骤如下：

• 给定两个正整数，先判断这两个数是否都是偶数，若都为偶数，这两个数同时除以2，直到不满足两个数都为偶数这一条件（记除以2的次数为n），然后进行第2步
• 若两个数不都为偶数，用 a 去减 b ，得到差 c ，然后把 b, c 按大小分配给 a , b ， 重复这一过程，直到 a b 相等为止

则最大公约数为除了多少次2的乘积再乘以相等的数，即：

算法模板

int gcd(int a, int b) {
    if(a < b)   swap(a, b);
    int n = 0;
    while(a%2==0 && b%2==0) {
        a /= 2;
        b /= 2;
        n++;
    }
    while(a != b) {
        a = a - b;
        if(a < b)   swap(a, b);
    }
    return pow(2, n) * a;
}