C语言求最大公约数和最小公倍数(思路清晰+拓展)[通俗易懂]

C语言求最大公约数和最小公倍数(思路清晰+拓展)[通俗易懂]最大公约数的求法首先了解它的一般求法(欧几里得算法):假设存在两个数A和B,假如A%B的结果不为0,那么A和B的最大公约数是B与A%B的最大公约数,一直往下计算,直到后者为0,此时的最大公约数为A’(注意不是A而是A’)。就比如上边的例子,当A%B==0的时候,最大公约数就是B了,这个A’就代表B。最大公约数的代码:(基于C++实现的函数)intgcd(inta,intb){ in…

大家好,又见面了,我是你们的朋友全栈君。

最大公约数的求法

首先了解它的一般求法(欧几里得算法):假设存在两个数A和B,假如A%B的结果不为0,那么A和B的最大公约数是B与A%B的最大公约数,一直往下计算,直到后者为0,此时的最大公约数为A’(注意不是A而是A’)。就比如上边的例子,当A%B==0的时候,最大公约数就是B了,这个A’就代表B。

最大公约数的代码:(基于C++实现的函数)

int gcd(int a,int b)
{
	int g;
	if(b==0)g=a;
	else g=gcd(b,a%b);
	return g;
}

最小公倍数与最大公约数的关系:

假设存在两个数A和B,那他们的最大公倍数就是A和B的积除以的A和B最大公约数即A*B/gcd(A,B)

有了上边求最大公约数的基础,那么我们就可以很轻松的求出两个数的最小公倍数了!不多说,上代码(基于C++语言实现的函数):

int mingbs(int a,int b)
{
	return a*b/gcd(a,b);//gcd函数在上边
}

最大公约数的性质的拓展:

其实求最大公约数是一件很简单的事情,但是它背后的数学性质也很重要;我在这里浅谈一下我曾经应用到的它的性质。

性质1:假如两个数的最大公约数是1,那么这两个数互质。
性质2:假如两个数互质(性质1),那么这两个数组成的最大的不可能的数是他们的积减去他们的和;反之则没有能够组成的最大不可能数,即不可能组成的数是无穷。

由于我没接触到它的别的性质,等我接触到后再补充。
上述两条性质再蓝桥杯的题目《包子凑数问题》中应用比较经典,因为它与动态规划联系起来运用了,有兴趣的读者可以去尝试解决,这样可以提高自己的编程应用能力。《包子凑数问题》请等待我有时间后,再与读者朋友们分享一下我的解题方法。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/145688.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号