[C++知识库]C语言求两数的最大公约数

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。 求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

一、直接求解法

1.明白最大公约数的定义后，我们知道任意两个数都有一个公约数1，若两数字无其他公约数，则1为最大公约数，所以对c初始化为1。如果x能被y整除或者y能被x整除，则x或y为他们两的最大公约数。

2.定义mi=Mi(x,y),即mi为x,y中较小的那个数字。

3.使用for循环求解，i从1开始循环，到mi停止（因数不可能比原数字中的任何一个大），所以如果能整除，则把i记录到变量c当中。

4.最后返回c，因为i是递增的，所以最后返回c的也一定是最大的那个因数。

int Mi(int a, int b)
{
	return a > b ? a : b;	
}
int Gcd(int x, int y)
{
	int mi = Mi(x, y);
	int c = 1;
	if (x % y == 0)
	{
		return y;
	}
	else if(y%x==0)
	{
		return x;
	}
	for (int i =2; i < mi; i++)
	{
		if (x%i==0&&y%i==0)
		{
			c = i;
		}
	}
	return c;
}
int main()
{
	int x = 0;
	int y = 0;
	
	printf("请输入两个数来寻找他的最大公约数（空格隔开）:");
	scanf("%d %d",&x,&y);
	printf("%d和%d的最大公约数是：%d",x,y,Gcd(x,y));
	return 0;
}

二、使用欧几里得（辗转相除法）

1.首先了解辗转相除法,欧几里得算法是用来求两个正整数最大公约数的算法。

假如需要求 648?和 156 两个正整数的最大公约数,用欧几里得算法，是这样的：

648 / 156 = 4 （余24）

156 / 24 = 6 （余12）

24 / 12 = 2（余0）

至此，最大公约数为12

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 648?和 156?的最大公约数 12。

设计函数内容：

如果a%b=0，则b是最大公约数，若不为，则将b的值赋值给a，a%b的值赋值给b

源码如下：

int Gcd(int a, int b)
{
	if (a % b == 0)
	{
		return b;
	}
	return Gcd(b, a % b);
}
int main()
{
	int x = 0;
	int y = 0;
	printf("请输入两个数来寻找他的最大公约数（空格隔开）:");
	scanf("%d %d", &x, &y);
	printf("%d和%d的最大公约数是：%d", x, y, Gcd(x, y));
	return 0;
}

不使用递归也可通过普通的循环语句实现：

int Gcd(int a, int b)
{
	int c = 0;
	for (;;)
	{
		if (a % b == 0)
		{
			return b;
		}
		c = a % b;
		a = b;
		b = c;
	}
	
	
}