C语言—求最大公约数（4种算法思路）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言—求最大公约数（4种算法思路）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.穷举法

如果大数可以整除小数，那么最大公约数为小数。如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。

int gcd(int a, int b)
{
	int i;
	int min = a < b ? a : b;
	for (i = min; i >= 1; i--)
	{
		if (a % i == 0 && b % i == 0) 
            break;
	}
	return i;
}

2.辗转相除法

用a对b求余，若余数为0，则除数b为最大公约数。若余数不为0，将此余数r作为新的除数，b作为新的被除数，重新求余，直到余数为0为止。此时的最大公约数为除数。

a.常规辗转

int gcd(int a, int b)
{
	int t;
	while(a % b)//当a%b为0时，跳出循环，最大公约数为b
	{
		r = a % b;
		a = b;
		b = t;
	}
	return b;
}

b.递归辗转

int gcd(int a, int b)
{
	int r = a % b;
	if (0 == r)
		return b;//当余数为0时，b就为最大公约数
	else
		return gcd(b, r);
}

3.更相减损法

当两个数相等时，最大公约数为他们其中任意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，任意一个都是最大公约数。文章来源地址https://www.toymoban.com/news/detail-849921.html

a.常规

int gcd(int a, int b)
{
	if (a > b) a = a - b;
	if (a < b) b = b - a;
	if (a == b) return a;
}

b.递归

int gcd(int a, int b) 
{
    if (a == b) return a;//当a=b时，返回
    if (a < b) 
    {
        return gcd(a, b - a);
    }
    return gcd(a - b, b);
}

4.质因数分解法

int gcd(int a, int b) 
{
    int result = 1, i;
    for (i = 2; i <= a && i <= b; i++) 
    {
        while (a % i == 0 && b % i == 0)
        {
            result *= i;
            a /= i;
            b /= i;
        }
    }
    return result;
}

到了这里，关于C语言—求最大公约数（4种算法思路）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！