最大公约数最小公倍数高效率算法

最大公约数最小公倍数高效算法

一般来说求两个数最大公约数，我们最先想到的是先找到两个数中较小的数，

然后从较小的数开始递减暴力搜索，如果能同时被两个数整除，那么这个数就是最大公约数，不能则继续递减。

但是当两个数很大的时候，这个算法的效率就变得很差，这时我们就需要一个高效算法。

这里我们利用的是中国古代的辗转相除法，关于辗转相除法的思想可以自行百度，我在这里直接贴代码

#include<stdio.h>
int gcd(int a, int b){
	if (a == 0) return b;
	return gcd(b % a, a);
}
int main(){
	printf("%d", gcd(40, 15));
	return 0;
}

用这个递归的方法我们不用考虑a是否小于b，我们假设a大于b，

那么在第一次递归的时候，a和b自然就交换了

接下来就是求最小公倍数，

有了最大公约数，那么最小公倍数就非常好求，

因为 a * b / gcd(a, b) 就是最小公倍数