最大公约数

2021-06-26

读了这篇博客文章，你将了解用一行代码求出两个数的最大公约数

最大公约数的求法，我查找资料之后，发现我们小学学的哪种只是最简单的一种方法，可能一部分人了解过第二种方法，今天要说的是对程序很友好的一种最大公约数求法。return t2 == 0 ? t1 : gcd(t2, t1 % t2);

检验公约数法

“检验公约数法“即“试除法”，也是小学数学课本价绍的哪一种一般的求法，比如我们求一个数的所有公约数就是使用这种方法。

先把各数分解质因数，再把各数共有的一切质因数连乘起来，就是所求的最大公约数。例如，求2940、756和168的最大公约数

2940=2^3*3*5*7^2,
756=2^2*3^3*7
168=2^3*3*7;
(2940,756,168)=2^3*3*7=84

注：(2940,756,168)=2^3*3*7=84 的意思，就是 “2940、756和168 的最大公约数是 84“

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

较大的两个数求最大公约数，可以用 “辗转相减法 ”：用大数减小数，如果减得的差与较小的数不相等，便再以大减小求差，直到出现两数相等为止。这是，相等的数就是这两个数的最大公约数。

例如，求792和594的最大公约数。如果用循环累死

=(198,594)=(594-198,198)
=(198,396)=(198,396-198)
=(198,198)=198，
(792,594)=198。

由于程序代码相比于普通的加减乘除更加灵活还有进制等，对于辗转相减法转换到程序就出现了几种不同的算法，例如更相减损法，穷举法，辗转相除法，我要说的是辗转相除法，想了解其他算法。

思路：

1、将两整数求余 t1%t2

2、如果t1%t2 = 0;则t2为最大公约数

3、如果t1%t2 != 0,则 t1 = t2；t2 = t1%t2；继续从第一步开始执行

4、也就是说该循环的是否继续的判断条件就是t1%t2是否为0

写成代码思路就是一个方法

1
2
3

int gcd(int t1, int t2) {
	return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}