求最大公约数你只会用内置函数吗？这三种方法让你有更多的选择

最大公约数（GCD, Greatest Common Divisor），下文简称GCD，指某几个整数共有约数中最大的那个。

一、穷举法

这是最直接暴力的方法。从1开始，到a和b中较小的那个数结束，看能不能同时被a， b整除，如果能，即为公约数，这样一个循环下来，一定可以找到GCD。

inline int gcd(int a, int b){
	int smaller = a < b ? a : b;  //先找出a和b中较小的那个
	int gcd = 1;
	for(int i = 2; i < smaller; i++){
		if((a % i == 0) && (b % i == 0))  //如果能除尽a和b，就更新gcd
			gcd = i;
	}
	return gcd;
}

二、辗转相除法

该方法又叫欧几里得法。

我们做一个推导：不失一般性，假设 a > b且 b != 0 ，记整数 a和 b的最大公约数是函数 gcd(a, b)。假设它们之间存在关系

                              a = b * k + r

这里 k是倍数，是一个整数（k = a / b），r是余数（r = a % b），也是一个整数。

用记号 |表示整除关系，例如 2 | 6。

看等式右边，根据定义 gcd(b,r)既是 b的因数，也是 r的因数，所以一定是 b 和 r的线性组合的因数，故 gcd(b,r) | a，根据定义 gcd(b,r) ，即 gcd(b,r)是两个数 a、b的公因数，故 gcd(b,r) | gcd(a,b)。

事实上，等式中 a 和 r 是地位相当的，做个等价变形 r = a - b * k，根据上面同样的思路，看右边：gcd(a,b)|r，并且 gcd(a,b)|b，故 gcd(a,b)|gcd(b,r)。

两个整数互相可以整除，那么它们要么相等，要么互为相反数。事实上，由于正负数不是研究公约数问题的核心，很多资料都会强制规定公约数是正数。因此 gcd(a,b)=gcd(b,r)。

由于编程语言中提供了求余数运算，因此，这样的等式可以一直做下去：

   gcd(a, b) = gcd(b, a % b) = ... = gcd(非零整数, 0)) = 非零整数

由于除数和余数是交替出现在等式中的，这个方法就被称之为「辗转相除法」。求解的过程显然是一个递归结构，并且递归终止条件是除数 b == 0。

有了理论基础，下面就总结成算法步骤：

1、a % b得余数 r；

2、若r == 0，则b即为gcd；

3、若r != 0，则a = b， b = r，返回步骤1.

迭代写法

inline int gcd(int a, int b){
	while(b > 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

递归写法

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

三目运算符

inline int gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
}

三、更相减损法

更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

看一下下面这两个例子：

例1：求25和15的最大公约数：

25 - 15 = 10 （10 < 15）

15 - 10 = 5 (5 <10)

10 - 5 = 5 (5 == 5)

所以，算得25和15的最大公约数是5。

例2：用更相减损术求260和104的最大公约数。

解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。

此时65是奇数而26不是奇数，故把65和26辗转相减：

65-26=39

39-26=13

26-13=13

所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即1322=52。

迭代写法

inline int gcd(int a, int b){
	if((a&1==0) && (b&1==0)){    //若两个整数都是偶数，则用2约简(不过用2化简不是必须的。)
		a >>= 1;
		b >>= 1;
	}
	while(a != b){              //如果ab不相等，就用大的减去小的，直到相等为止
		if(a > b)	a -= b;
		else	b -= a;
	}
	return a;
}

递归写法

inline int gcd(int a, int b){
	if(a == b)	return a;  
	return a > b ? gcd(a - b, b) : gcd(a, b - a);   //这里不化简处理，直接相减
}

比较辗转相除法与更相减损术的区别

（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

另补充：algorithm.h 头文件中的函数

__gcd(x, y)      //注意是两个下划线，这个可以直接调用，返回x和y的最大公约数

例如：

#include <algorithm>
inline int gcd(int a,int b) {
	return __gcd(a,b);
}

当需要计算多个数的公约数时，先求前两个的最大公约数，依次和后面的数求公约数，得到的就是所有数字的最大公约数。