求最大公约数（辗转相除法）_辗转相除法求最大公约数

一、何为最大公约数、辗转相除法

1、最大公约数也叫做最大公因数，两者意思一致，指两个或多个整数共有的约数中最大的一个。

2、辗转相除法，又叫欧几里得算法，在介绍原理之前我们先假定（a, b)为a和b的公约数

原理：（a, b)=(a, ka+b)，即a和b的公约数与a和ka+b的公约数相同，基于这个原理，我们可以看到（24，16）=（8，16）=（8，8）=（8，0）最终24和16的最大公约数是8，即求两个数的最大公约数，可以不断用大的数减去小的数，从而最终得到最大公约数。而上面迭代相减的过程，我们完全可以用除法来得出，因为（24，16）=（1x16+8，16）=（8，16），而且显然易见的，除法的操作次数比减法更少，因而诞生了辗转相除法。

二、代码示例

1、循环做法

// 循环做法
int gcd(int a, int b) {
	int m = max(a, b); //得到两数中较大的一个
	int n = min(a, b); //得到两数中较小的一个
	int r = m % n; //大的数除以小的数
	while (r != 0) {
		m = n; //m成为新一轮除法中较大的数
		n = r; //n成为新一轮除法中叫小的数
		r = m % n; //再一次大的数除以小的数
	}
	return n; //多次辗转后得到最终余数
}

2、递归做法

// 递归做法
int gcd(int a, int b) {
	int m = max(a, b); //得到两数中较大的一个
	int n = min(a, b); //得到两数中较小的一个
	if (m % n == 0)
		return n;
	return gcd(n, m % n); //返回两个小的数
}

三、总结

总之，学会辗转相除法的关键在于明白其原理，笔者之前因为没有明白其原理，囫囵吞枣的看一下，以致重重复复忘了几次，望诸君以此为恶，真真正正学到知识！