C语言求最大公约数(四种)

前言：

设两数分别为a和b，运行时间中，输入时间不算在内

(1)九章算术—更相减损法

判断a和b那个大,然后大数就减去小数的,再将减去得到的值赋予大数的位置,继续判断,直至两数相等,这时,a=b=最大公约数

适用于两数相差不大也不小

例:

如果a>b,则a=a-b;

如果吧b>a,则b=b-a;

当a,b相等时,最大公约数就是a或b(a,b相等)

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	while (a != b)
	{
		if (a > b)
			a -= b;
		else
			b -= a;
	}
	printf("%d", a);
}

时间复杂度 = O (log (max (a, b)))

算法优缺点:很稳定，但是数据大了就很慢

比较平衡的算法,避免了模运算,且算法性能平稳.

(2)单相取余法

先判断a,b那个大,再用a和b的对小的取余,如果结果不为0,则让小的数-1,直至结果为0.

适用于两数相差较大,且其中一个数在数轴上离0比较近

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	int n = a > b ? b : a; //最小值
	while (a % n != 0 || b % n != 0)
		--n;
	printf("%d", n);
}

优点:算法设计简单且稳定,时间复杂度 = O(min(a,b))<O(log(max(a,b)))所以比更相减损发快

缺点:因为时间复杂度 = O(min(a,b)),所以最小值越大,计算越慢

(3)欧几里得——辗转相除法

让两个数中的大数对小数取余,再将小数赋予大数,结果赋予小数,重复以上动作直至两数其中一个数为零,那么另一个就是最大公约数

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	while (a && b)
	{
		if (a > b)
			a %= b;
		else
			b %= a;
	}
	printf("%d", a>b?a:b);
}

优点:时间复杂度 = O(logn)适用于大部分范围

缺点:如果遇到相差比较大的数,计算起来就会开始慢了

(4)函数递归法

通过函数调用自身达到求最大公约数的目的,运行速度快,但是不稳定

适用于两数相差较小时求最大公约数.

int fin(int a, int b)
{
	if (a > b)
		fin(a - b, b);
	else if (a < b)
		fin(b - a, a);
	else
		return a;
}

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", fin(a,b));
}

栈溢出，不参与运行时间统计

优点:时间复杂度=O(1),速度非常快

缺点:需要注意栈溢出,且两数不能与0相差太远,否则一定栈溢出!!

总结:在数值较小的两个公因数之间,可以优先选择递归或者单相取余法;若是数值比较大,则优先选择辗转相除法;若数值飘忽不定,辗转相除法和更相减损法依情况而定.