目录

前言

一、枚举法

二、辗转相除法

三、更相减损法

---

---

前言

如何求两个数的最大公约数是非常经典的问题，求解的方法也有很多，本文主要介绍其中的三种方法，分别是：枚举法、辗转相除法和更相减损法。

 

一、枚举法

两个数的最大公约数一定小于或等于两数中较小的数，并且这两个数必定至少存在一个公因数 1，利用这两个条件，可以将两个数的最大公约数的所有可能都列举出来。

#include <stdio.h>

int main()
{
	int a = 0;
	int b = 0;
	int min = 0;
	scanf("%d%d", &a, &b);
	if (a > b)
		min = b;
	else
		min = a;
	for (int i = min; i > 0; i--)  // i：min -> 1
	{
		if (a % i == 0 && b % i == 0)
		{
			printf("的最大公约数为 %d", i);
			break;
		}
	}
	return 0;
}

二、辗转相除法

辗转相除法，又名欧几里得算法，是求最大公约数的一种算法。辗转相除法首次出现于欧几里得的《几何原本》中的第 Ⅶ 卷，书中的命题 i 和命题 ii 所描述的就是辗转相除法。

辗转相除法的本质就是：用一个数除以另一个数，如果余数不为 0，则用除数除以余数，一直反复，直到余数为 0 为止，即 a % b = r1，若 r1 ≠ 0，则用 b % r1 = r2，若 r2 ≠ 0，那么一直反复，直到某个余数 rn 为0 为止，最后一条式子的除数就是两个数的最大公约数。

把两个数看作被除数与除数的关系，则两个数的最大公约数就等于除数与余数的最大公约数，即 gcd(a, b) = gcd(b, r)。

辗转相除法源于希腊，希腊人非常喜欢从图形或者是用几何的角度去看待问题，很多希腊数学家都习惯先去思考能否将其转换为直观的几何图形再进行求解。所以很自然地，希腊数学家在面对求两个数的最大公约数这个问题时，也首先去思考这个问题是否能通过将其转换成一个几何问题来处理。在经过一些尝试之后，这一设想最终实现了，希腊数学家将所要求最大公约数的两个数字 a 和 b 分别作为矩形的两条边，那么这个问题就被转换成在这个矩形中找到这样一个正方形，这个正方形能够没有缝隙地铺满上述矩形，显然这类正方形可能有多个（当然，也只考虑正整数边长的正方形），而我们的目标就是找出这类正方形中最大的那一个。

那么我们如何找到这样一个正方形呢？具体操作如下：

证明：我们假设 a = 16，b = 6，两个数的最大公约数为 c。

显然 c <= b，因此我们先用矩形的短边 b 构造正方形，然后判断这样的正方形能否铺满整个矩形，判断方式可以是计算两个数的余数。因为 a ÷ b = n ... r，余数 r 不为零，所以 c ≠ b。又因为 a = k1c，b = k2c，r = a - n·b = k1c - nk2c = (k1 - nk2)c，所以 c 也是余数 r 的约数，那么 c <= r，因此再用余数 r 构造正方形，判断这样的正方形能否铺满以 b 和 r 为边的小矩形，即计算 b % r 的结果。

用余数 r 构造的正方形如果能铺满以 b 和 r 边的小矩形，则一定能铺满整个大矩形。

一直反复，直到余数为 0 为止，最后能铺满矩形的正方形的边长就是 a 和 b 的最大公约数。

#include <stdio.h>

int main()
{
	int a = 0;
	int b = 0;
	int r = 0;
	scanf("%d%d", &a, &b);
	while ((r = a % b) != 0)  
	{
		// 若余数不为 0
		a = b;
		b = r;
	}
	// 当余数为 0 时，除数就是两数的最大公约数
	printf("最大公约数是 %d\n", b);
	return 0;
}

三、更相减损法

更相减损术是出自《九章算术》的一种求最大公约数的算法，其本质是：以较大的数减去较小的数，接着把所得的差与较小数相比较，并以较大数减较小数，继续这样的操作，直到所得的减数和差相等为止，即若 a > b，a - b = s1（s1 ≠ 0），若 b > s1，b - s1 = s2（s2 ≠ 0），若 s1 = s2，s1 - s2 = 0，那么 s1、s2 就是 a 、b 的最大公约数。

#include <stdio.h>

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	while (a != b)
	{
		if (a > b)
			a -= b;  // 当 a > b 时，a 来保存两数的差
		else
			b -= a;  // 当 a < b 时，b 来保存两数的差
	}
	printf("最大公约数是 %d", a);
	return 0;
}