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
{
t = 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.更相减损法
当两个数相等时，最大公约数为他们此中恣意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，恣意一个都是最大公约数。
a.常规
int gcd(int a, int b)
{
do
{
if (a > b) a = a - b;
if (a < b) b = b - a;
}while(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;
i = 1;
}
}
return result;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]