C语言—求最大公约数（4种算法思绪）

1.穷举法

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

1. int gcd(int a, int b)
2. {
3.         int i;
4.         int min = a < b ? a : b;
5.         for (i = min; i >= 1; i--)
6.         {
7.                 if (a % i == 0 && b % i == 0)
8.             break;
9.         }
10.         return i;
11. }

复制代码

---

2.辗转相除法

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

1. int gcd(int a, int b)
2. {
3.         int t;
4.         while(a % b)//当a%b为0时，跳出循环，最大公约数为b
5.         {
6.                 t = a % b;
7.                 a = b;
8.                 b = t;
9.         }
10.         return b;
11. }

复制代码

b.递归辗转

1. int gcd(int a, int b)
2. {
3.         int r = a % b;
4.         if (0 == r)
5.                 return b;//当余数为0时，b就为最大公约数
6.         else
7.                 return gcd(b, r);
8. }

复制代码

3.更相减损法

当两个数相等时，最大公约数为他们此中恣意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，恣意一个都是最大公约数。
a.常规

1. int gcd(int a, int b)
2. {
3.         do
4.     {
5.         if (a > b) a = a - b;
6.             if (a < b) b = b - a;
7.         }while(a != b);
8.     return a;
9. }

复制代码

b.递归

1. int gcd(int a, int b)
2. {
3.     if (a == b) return a;//当a=b时，返回
4.     if (a < b)
5.     {
6.         return gcd(a, b - a);
7.     }
8.     return gcd(a - b, b);
9. }

复制代码

---

---

4.质因数分解法

1. int gcd(int a, int b)
2. {
3.     int result = 1, i;
4.     for (i = 2; i <= a && i <= b; i++)
5.     {
6.         while (a % i == 0 && b % i == 0)
7.         {
8.             result *= i;
9.             a /= i;
10.             b /= i;
11.             i = 1;
12.         }
13.     }
14.     return result;
15. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。