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为止。此时的最大公约数为除数。文章来源:https://www.toymoban.com/news/detail-849921.html
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模板网!