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

最大公约数的求法

首先了解它的一般求法（欧几里得算法）：假设存在两个数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账号...