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

最大公约数是两个数可以同时整除的数中最大的那个 这里用三种方法来解决

1. 穷举法求最大公约数 判断x和y的最大公约数，x和y其中一定有一个相对较小的数，然后从这个较小数开始遍历，不断地用x和y去除这个数，直到可以同时整除，那么就得出了最大公约数。

#include <stdio.h>

int MyGCD(int _x, int _y)   //定义一个函数求两个数的最大公约数
{
          
   
	if (_x > _y)  //进行交换，保证_x是两个数中较小的一个方便后面遍历
	{
          
   
		int temp = _x;
		_x = _y;
		_y = temp;
	}
	int i = 0;
	for (i=_x; i >0; i--)   //找出最大公约数
	{
          
   
		if (_x%i == 0 && _y%i == 0)
		{
          
   
			return i;
		}

	}
	return 0;
}

int main()
{
          
   
	printf("请输入两个要判断的数：");
	int x = 0;
	int y = 0;
	scanf("%d %d", &x, &y);  //输入两个要判断的数
	int result = MyGCD(x, y);
	printf("最大公约数是：%d
", result); 
	return 0;
}

2. 辗转相减法求最大公约数 假设两个数x和y的最大公约数为t，那么x=m1*t，y=m2*t，我们假设x小于y，用y减去x还剩下（m2-m1）个t，这样一直减，直到一个数减为0，另一个数剩下的就是1个t，得出最大公约数。

#include <stdio.h>

int MyGCD(int _x, int _y)
{
          
   
	while (_x * _y != 0)   //判断_x和_y都不为0
	{
          
   
		if (_x > _y)    //辗转相减
		{
          
   
			_x = _x - _y;
			//也可以简写成_x-=_y;
		}
		else if(_x < _y)
		{
          
   
			_y = _y - _x;
			//也可以简写成_y-=_x;
		}
		else
		{
          
   
			return _x;   //如果两数相等，则任意返回_x或_y是一样的
		}
	}
	return _x == 0 ? _y: _x;
}

int main()
{
          
   
	printf("请输入两个要判断的数：");
	int x = 0;
	int y = 0;
	scanf("%d %d", &x, &y);
	int result = MyGCD(x, y);
	printf("最大公约数是：%d
", result);
	return 0;
}

3. 辗转相除法求最大公约数 假设两个数x和y的最大公约数为t，那么x=m1*t，y=m2*t，我们假设x小于y，用y去除x还剩下（m2/m1）个t，这样一直相除，直到一次除完之后模0，没有余数，赋值之后有一个数为0，另一个数剩下的就是1个t，得出最大公约数。

#include <stdio.h>

int MyGCD(int _x, int _y)
{
          
   
	while (_x*_y!=0)
	{
          
   
		if (_x > _y)
		{
          
   
			_x %= _y;
		}
		else if(_x < _y)
		{
          
   
			_y %= _x;
		}
		else
		{
          
   
			return _x;
		}
	}
	return _x == 0 ? _y: _x;
}

int main()
{
          
   
	printf("请输入两个要判断的数：");
	int x = 0;
	int y = 0;
	scanf("%d %d", &x, &y);
	int result = MyGCD(x, y);
	printf("最大公约数是：%d
", result);
	return 0;
}

辗转相减法和辗转相除法的代码很像，但是辗转相除法会相对来说效率更高一点，计算的会比辗转相除法次数少。