C语言中利用辗转相除法求最大公约数

1. 首先要明确几个概念：

最大公约数： 也叫最大公因数，是指俩个或多个整数公有约数中最大的一个。

例如，18 和 24的最大公约数是 6

最小公倍数：除0以外最小的一个公倍数就叫作这几个整数的最小公倍数

例如，18 和 24的最小公倍数是 72

2. 辗转相除法：

用除数和余数反复做除法运算，当余数为0时，取当前算式除数为最大公约数

例如：求 1997 和 615 俩个正整数的最大公约数

因为：

1997 % 615 = 152

615 % 152 = 7

152 % 7 = 5

7 % 5 = 2

5 % 2 = 1

2 % 1 = 0

所以，1997 和 615 的最大公约数为 1

3. C语言代码实现：

#include <>
int main()
{
	int data1 = 0, data2 = 0;
	int m = 0;     //该变量是中间变量，不能放在while函数的内部
	scanf_s("%d %d", &data1, &data2);

	while ((m = data1 % data2) != 0)
	{
		data1 = data2;
		data2 = m;
	}

	printf("最大公约数为%d\n", data2);
	return 0;
}

注意点：

对于求模运算符%，若是分数形式求余数的话，如果分子小于分母，则分子就是余数。

例如：2 % 5 = 0

而当不是分数形式求余数的话，即例如：18 % 24 时，可将 % 左边的内容看成是分子，而 % 右边的内容看成是分母。所以 18 % 24 = 18

这里有一个误区，不能将18 与 24 在都约去 6 的情况下去求它们的余数，所以 18 % 24（3 % 8）= 3 是错误的

而不管是 18 % 24 ，还是24 % 18 。它们的余数均不会成为0

如果知道了俩个数的最大公约数，那么其最小公倍数可以根据公式来确定

即最小公倍数 = 俩个数的乘积 / 最大公约数