C语言中求两数最大公约数的三种方法

1.穷举法

思路：

首先对输入的两个数x,y判断两者的大小，取两者中较小的数放入i中。然后用x%i;y%i，如果两者都为0，则此时i为最大公约数。如果其中有一个不为0，则i减1后再用x,y分别模上i（注意此时的i为x,y中的较小值，并不为1），如果其中有一个不为0，则i继续减1，以此类推直到x%i,y%i，两者都为0，此时的i即为两数的最大公约数。

int main()
{
	int x = 0;
	int y = 0;
	int i = 0;
	scanf("%d %d",&x, &y);
	//求得两者中的较小值
	if (x > y)
	{
		//从i等于较小值开始循环
		for (i = y; i >= 1; i--)
		{
			if (x % i == 0 && y % i == 0)
			{
				printf("最大公约数是:%d", i);
				break;
			}
		}
	}
	//从i等于较小值开始循环
	else
	{
		for (i = x; i >= 1; i--)
		{
			if (x%i==0&&y%i==0)
			{
				printf("最大公约数是:%d", i);
				break;
			}
		}
	}
	return 0;

2.更相相减法

思路：

首先将输入的两数a,b相减，等于0则最大公约数即为a=b，如果不等于0则进入循环。在循环中先判断两者大小，再将较大值减去较小值的出来值赋给较大值。然后再用新得出来的较大值与原较小值相减，如果不等于0则进入循环，以此类推，直到新得出来的较大值与原较小值相减为0，此时最大公约数即为新较大值=原较小值。

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	while ((a - b) != 0)
	{
		//判断两数大小
		if (a > b)
		{
			//将较大值赋较大值减去较小值得出来的值
			a = a - b;
		}
		else
		{
			//将较大值赋较大值减去较小值得出来的值
			b = b - a;
		}
	}
	printf("%d", b);
		return 0;

3.辗转相除法

思路：

首先对输入的两数a,b判断大小，然后将较大值模上较小值得出值c。如果c等于0，则最大公约数即为a=b。如果c不等于0，则进入循环将原较小值赋给新较大值，将值c赋给新较小值，然后再将新较大值模上新较小值得出来的值赋给c，如果c还是不为0则再进入循环，以此类推，直到c等于0.此时最大公约数为a=b。

nt main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	//判断两者大小
	if (a >= b)
	{
		//将较大值模上较小值得出来的值赋给c
		int c = a % b;
		//判断c是否为0
		while (c != 0)
		{
			//将原较大值，原较小值分别赋值
			a = b;
			b = c;
			//将较大值模上较小值得出来的值赋给c
			c = a % b;
		}
		printf("最大公约数为：%d", b);
	}
	else
	{
		int d = b % a;
		while (d != 0)
		{
			b = a;
			a = d;
			d = b % a;
		}
		printf("最大公约数为：%d", a);
	}
	return 0;
}