求最大公约数（C）

求最大公约数（C）

C语言求最大公约数

前言一、普通方法二、辗转相除法总结

---

前言

最大公约数，指某几个整数共有因子中最大的一个。
例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。

---

一、普通方法

声明一个整型变量max表示两者的最大公约数，因为两个整数的最大公约数肯定小于或等于两者中的最小值，如12和36的最大公因数有1，2，3，4，6，12，所以max存放的是两者中的最小值。在while循环中不断判断两个整数能否整除max，如果不行max就减一，必定会减到1，满足if条件后退出循环

代码如下（示例）：

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	//假设最大公约数是a,b中的最小值
	int max = a > b ? b : a;
	while (1)
	{
		if (a % max == 0 && b % max == 0)
		{
			printf("最大公约数是：%dn", max);
			break;
		}
		max--;
	}
	return 0;
}

---

二、辗转相除法

声明一个中间变量temp,将a%b的值赋给temp，在while循环中判断如果temp不为0，则将b的值赋给a，将余数temp赋给b，再进行循环，直到temp等于0，退出循环，此时b的值就是最大公约数。

代码如下（示例）：

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	int temp = 0;
	while (temp = a % b)
	{
		a = b;
		b = temp;
	}
	printf("最大公约数是%dn", b);
	return 0;
}

---

总结

两种方法都可以，辗转相除法更为快捷。