大家好，又见面了，我是你们的朋友全栈君。
最大公约数的求法
首先了解它的一般求法（欧几里得算法）：假设存在两个数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），那么这两个数组成的最大的不可能的数是他们的积减去他们的和；反之则没有能够组成的最大不可能数，即不可能组成的数是无穷。
由于我没接触到它的别的性质，等我接触到后再补充。
上述两条性质再蓝桥杯的题目《包子凑数问题》中应用比较经典，因为它与动态规划联系起来运用了，有兴趣的读者可以去尝试解决，这样可以提高自己的编程应用能力。《包子凑数问题》请等待我有时间后，再与读者朋友们分享一下我的解题方法。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/145688.html原文链接：https://javaforall.net
