辗转相除法求解最大公约数、最小公倍数

辗转相除法求解最大公约数、最小公倍数

通常来说，求解两个数的最大公约数和最小公倍数是常见的算法问题，我们正常人最先想到的肯定是穷举法，通过while循环或者for循环，不断改变循环数，辗转取余判断是否为0。C++代码如下：

// An highlighted block
#include<iostream>
using namespace std;
//求解最大公倍数
int gcd1(int a, int b)
{int maxfac = b;while (maxfac>=1){if (a%maxfac == 0 && b%maxfac == 0)return maxfac;elsemaxfac--;}return 1;
}
//求解最小公约数
int gcd2(int a, int b)
{int minmul = a;while (minmul <= a*b){if (minmul%a == 0 && minmul%b == 0)return minmul;elseminmul++;}return a*b;
}int main()
{int a, b;cin >> a >> b;int temp;//设置a为两个数中较大的数，b设置为较小的数if(a<b){temp = a;a = b;b = temp;}cout << "最大公约数: " << gcd1(a, b) << endl;cout << "最小公倍数: " << gcd2(a, b) << endl;system("pause");return 0;
}

但是在实际的算法题中，这种算法时间复杂度较高，如果给定的数值较大，计算指定超时，而且体现不出算法的技巧性。所以衍生出了稍微有一点技巧的辗转相除法求解最大公约数，以及通过最大公约数求解最小公倍数。C++代码如下：

#include<iostream>
using namespace std;int gcd(int a, int b)
{int temp;while (b){temp = a%b;a = b;b = temp;}return a;
}int main()
{int a, b;cin >> a >> b;int temp;if(a<b){temp = a;a = b;b = temp;}//设置a为两个数中较大的数，b设置为较小的数cout << "最大公约数: " << gcd(a, b) << endl;cout << "最小公倍数: " << (a*b) / gcd(a, b) << endl;system("pause");return 0;
}

首先降低了求解最大公约数的时间复杂度，同时求解最小公倍数的过程也可以通过最大公约数一步到位，两个过程合并为一个过程。
算法问题最近持续更新，大家可以关注我的CSDN博客。