Stackoverflow：计算两个整数的最小公倍数的最有效方法是什么？

嘿，小傅哥怎么突然讲到最大公约数了？,这么想你肯定是没有好好阅读前面章节中小傅哥讲到的RSA算法，对于与欧拉结果计算的互为质数的公钥e，其实就需要使用到辗转相除法来计算出最大公约数。,放心，你所有写的代码，都是对数学逻辑的具体实现，无非是难易不同罢了。所以如果你真的想学好编程思维而不只是CRUD，那就要把数据结构、算法逻辑等根基打牢。,既然都说到这了，那你还记得怎么计算最大公约数吗，死鬼？,,以上这种方式就是我们在上学阶段学习的，这种计算方式叫做短除法。,短除法：是算术中除法的算法，将除法转换成一连串的运算。短除法是由长除法简化而来，当中会用到心算，因此除数较小的除法比较适用短除法。对大部分的人而言，若除以12或12以下的数，可以用记忆中乘法表的内容，用心算来进行短除法。也有些人可以处理除数更大的短除法。—— 来自维基百科,短除法能解决计算最大公约数的问题，但放到程序编写中总是很别扭，总不能一个个数字去试算，这就显得很闹挺。其实除了短除法还有一种是计算公约数的办法，叫做欧几里德算法。,欧几里德算法：是计算两个整数（数字）的最大公约数【GCD(Greatest Common Divisor)】的有效方法，即能将它们整除而无余数的最大数。它以古希腊数学家 欧几里得的名字命名，欧几里德在他的几何原本（约公元前 300 年）中首次描述了它。它是算法的示例，是根据明确定义的规则执行计算的分步过程，并且是常用的最古老的算法之一。它可以用来减少分数到他们的最简单的形式，并且是许多其他数论和密码计算的一部分。—— 来自维基百科,GCD，代表了两个数字的最大公约数，GCD(X,Y) = Z，那么就表示 X 和 Y 的最大公约数是 Z。由欧几里德算法给出 GCD(X,Y) = GCD(Y,XmodY) —— mod 表示求模计算余数。,其实简单来说就是，X和Y的公约数是Z，那么Y和Z的公约数也是Z。24和18的最大公约数是6，那么18和6的公约数也是6。嘿，就这么一个事。但就因为有了这一样一条推论，让编程代码变得优雅舒服，只需要不断地将X、Y两数作差，就能计算最大公约数。,这让小傅哥想起，多年前上学时候，我也给出过一条推论；”任意一组所能构成等差数列的三个数字，所能组合出来的一个三位数，都能被3整除。“ 例如：等差数列 16、31、46 组合成三位数 463116 或者 461631 都能被3整除。,欧几里德算法 = 辗转相除法法：https://en.wikipedia.org/wiki/Euclidean_algorithm,在辗转相除法的实现中，计算最大公约数的方式，就是使用一个数字减去另外一个数字，直到两个数字相同或者有其中一个数字为0，那么最后不为零的那个数字就是两数的最大公约数。,小傅哥在这里提供了2种计算方式，一种是循环另外一种是递归。—— 方便很多看不懂递归的小伙伴可以用另外的方式学习。,测试结果,在 stackoverflow.com 看到一道问题：计算两个整数的最小公倍数的最有效方法是什么？,,乍一看， 这能有啥。不就是计算下最小公倍数吗？但一想我脑袋中计算最小公倍数的方法；一种是在本子上通过短除法计算，另外一种是基于计算出的最大公约数，再使用公式：lcm(a, b) = |a * b| / gcd(a, b) 求得最小公倍数。—— 计算最大公约数是基于欧几里德算法(辗转相除法),那么这样的计算方法是不是最有效的方法，另外如果是同时计算多个整数的最小公倍数，要怎么处理？,其实编程的学习往往就是这样，留心处处都是学问，你总是需要从各种细小的点中，积累自己的技术思维广度和纵向探索深度。好啦，接下来小傅哥就给大家介绍几种用于计算最小公倍数的算法。,公式：lcm(a, b) = |a * b| / gcd(a, b),此计算方式为，在一组正整数数列中，通过找到最小的数字进行自身累加循环，直至所有数字相同时，则这个数字为最小公倍数。—— 你能代码实现一下吗？,,表格计算方式为将一组数字以最小的质数2开始整除，直到不能被2整除后，用下一个质数3继续整除（剩余的数字中比大的最小的质数）直至所有数字都为1的时候结束。最终所有有效的质数乘积就是最小公倍数。—— 想想如果这让你用代码实现，你能肝出来吗？,