最大公约数和最小公倍数

       辗转相除法(欧几里得算法)算是求最大公约数最简单高效的算法了,这几行代码用最简洁的方式写了这个算法,值得牢牢记住:

#include <cstdio>

//最大公约数 

int Gcd(int a, int b)
{
	return b == 0 ? a : Gcd(b, a%b); 
}

//最小公倍数

int Lcm(int a, int b)
{
	return a / Gcd(a, b) * b; 
} 

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	int gcd = Gcd(a, b);
	printf("%d与%d的最大公约数为%d\n", a, b, gcd);
	int lcm = Lcm(a, b);
	printf("%d与%d的最小公倍数为%d\n", a, b, lcm);
	return 0;
}

       既然采用了递归,自然会想到会不会栈溢出,有人证明出,Gcd函数的递归层数不会超过4.785lgN + 1.6723(N = max(a,b))。

求最小公倍数可以用lcm = a*b / gcd,为了防止a*b过大溢出,常采用先除以最大公约数再乘以b的方式。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券