博客

1.辗转相除法：又称欧几里得算法，用于计算两个非负整数a，b的最大公约数。

定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

例如：

218 / 14=15……8

14 / 8=1……6

8 / 6=1……2

6 / 2=3……0

所以2是218和14的最大公约数，这和定理一模一样，218与14的最大公约数和6与2的一样，因为

两数相除余数为零时，其除数必为最大公因数

，因此2是6与2的最大公因数。以此也可以逆推也是8与6的最大公因数…,最终推出是218与14的最大公因数，这与定理结合起来看方便理解，就是一个

接一个一直用除数除以上一个式子的余数直到余数为零，就求出最大公因数了。

理论讲完了接着就是代码实现

#include<stdio.h>
int com(int x, int y)
{
	int q = 0;
	q = x % y;
	while (q > 0)
	{
		x = y;
		y = q;
		q = x % y;
	}
	return y;
}
int main()
{
	int m = 0;
	int n = 0;
	scanf_s("%d %d",&m,&n);
	int i = com(m, n);
	printf("%d\n",i);
}

此外还可以用更简单的递归实现:

#include<stdio.h>
int com(int x, int y)
{
	if (x % y == 0)
	{
		return y;
	}
	else
		return com(y, x % y);
}
int main()
{
	int m = 0;
	int n = 0;
	scanf_s("%d %d",&m,&n);
	int i = com(m, n);
	printf("%d\n",i);
}

运行结果如图。