8和2的最小公倍数

作者:肖福哥
博客:https://bug stack . cn-包括:Java基础、教材手册、Netty4.x、手写Spring、用Java实现JVM、重新学习Java设计模式、SpringBoot的中间件开发、IDEA插件开发、DDD系统架构项目开发、字节码编程。...

沉淀，分享，成长，让自己和他人都有所收获！

一、前言

哎，富哥怎么突然说起最大公约数了？

如果你是这样想的，那你一定没看过小富哥上一章提到的RSA算法。对于公钥E，这是一个用欧拉结果计算出来的素数，你实际上需要用除法来计算最大公约数。

不用担心，你写的代码都是数理逻辑的具体实现，只是难度不同而已。所以如果你真的想学好编程思维，而不仅仅是CRUD，你要在数据结构，算法逻辑等等方面打好基础。

二、短除法

既然说到这了，你还记得最大公约数怎么算吗，死鬼？

以上方法是我们在学校学的，这种计算方法叫短除法。

短除法:算术中除法的算法，将除法转化为一系列运算。短除法是由长除法简化而来，长除法会用到心算，所以除数较小的除法更适合短除法。对于大多数人来说，如果除以12以下的数，可以利用内存中乘法表的内容，通过仔细计算，进行短除法。有些人还能处理除数较大的短除法。-来自维基百科

三、欧几里德算法

短除法可以解决最大公约数的计算问题，但是放到编程中总是很别扭，总是无法把数字一个一个试出来，很吵。其实除了短除法还有一种计算公约数的方法，叫做欧几里德算法。

欧几里德算法:是计算两个整数(数)的最大公约数[GCD(大公约数)]的一种有效方法，即能在不求最大余数的情况下将它们整除。它以古希腊数学家欧几里得的名字命名，欧几里得在他的《几何原本》(约公元前300年)中首次描述了它。它是算法的一个例子，是根据明确定义的规则执行计算的一步一步的过程，是最古老的常用算法之一。它可以用来将分数简化为最简单的形式，也是许多其他数论和密码计算的一部分。-来自维基百科

GCD表示两个数的最大公约数，GCD (x，Y) = Z，那么就意味着X和Y的最大公约数是Z，通过欧几里德算法，GCD(X，y) = GCD (y，xmody)-mod代表模数计算余数。

其实简单来说，X和Y的公约数是Z，那么Y和Z的公约数也是..24和18的最大公约数是6，所以18和6的公约数也是6。嘿，就一件事。但正因为这样的推论，编程代码变得优雅舒适，不断地将X和y两个数相除，就能计算出最大公约数。

这让伏哥想起了很多年前我上学时的一个推论。能构成等差数列的任何一组三位数，和一个能组合的三位数，都能被3整除。比如算术级数16、31、46组合成三位数，463116或461631可以被3整除。

四、辗转相除法代码实现

欧几里德算法=相除:https://en.wikipedia.org/wiki/Euclidean_algorithm

在除法的除法实现中，计算最大公约数的方法是用一个数减去另一个数，直到两个数相同或其中一个为0，那么最后一个非零数就是两个数的最大公约数。

付晓师兄在这里提供了两种计算方法，一种是循环，一种是递归。-方便很多不懂递归的朋友用其他方式学习。

1. 循环实现

public long gcd01(long m，long n){ m = math . ABS(m)；n = math . ABS(n)；而(m！= 0 && n！= 0 && m！= n){ if(m & gt；n){ m = m-n；} else { n = n-m；} }返回m == 0？n:m；}在二数循环处理中，条件是m！= 0 && n！= 0 && m！= n直到循环结束。2.递归实现公共long gcd02 (long m，long n) {if (m

44以退出代码0结束的Process计算124和20的最大公约数，两种计算方法的结果都是4。好了，我通过了这里的测试。这并不是一个很难的知识点，但是当你做一些技术分享、答辩、述职的时候，你可以用技术语言而不是大白话来讲，其实可用性很高。兄弟！在stackoverflow.com看到一个问题:计算两个整数的最小公倍数最有效的方法是什么？

乍一看，这可能没什么。不就是为了计算最小公倍数吗？但是当我脑子里想着计算最小公倍数的方法的时候；一种是在笔记本上用短除法计算，另一种是根据计算出的最大公约数，然后用公式:lcm(a，b) = |a * b|/gcd(a，b)求最小公倍数。最大公约数的计算基于欧几里德算法(相除)

那么这种计算方法是不是最有效的方法呢？另外，同时计算多个整数的最小公倍数怎么办？

其实编程的学习往往是这样的。处处讲究知识。你总是需要从各种小点开始积累自己的技术思维广度和垂直探索深度。好了，接下来富哥给大家介绍几种计算最小公倍数的算法。

五、用公约数实现

公式:lcm(a，b) = |a * b|/gcd(a，b)

public long lcm01(long m，long n) { return ((m == 0) || (n == 0))？0 : Math.abs(m * n) / gcd(m，n)；}private long gcd(long m，long n){ m = math . ABS(m)；n = math . ABS(n)；//从一个数字中减去另一个数字，直到两个数字相同。//这将是GCD。如果其中一个数字为零，循环也将退出。//https://en.wikipedia.org/wiki/Euclidean_algorithm虽然(m！= 0 && n！= 0 && m！= n){ if(m & gt；n){ m = m-n；} else { n = n-m；} }返回m == 0？n:m；}首先，这里有一个比较简单的方法。基于两个数的乘积除以最大公约数，结果是最小公倍数。六、简单累加计算这种计算方法是在一组正整数数列中，找出最小的数进行自己的累加循环，直到所有的数都相同，那么这个数就是最小公倍数。-你能编码吗？

公共long lcm02(long...n){ long[]cache = n . clone()；//条件是所有数都相等而(！is equals(n)){ system . out . println(JSON . tojsonstring(n))；龙敏= n[0]；int idx = 0；for(int I = 0；我& ltn .长度；i++){ if(min & gt；n[I]){ min = n[I]；idx = I；} } n[idx]= cache[idx]+min；} return n[0]；}在代码实现中，首先要克隆N个整数序列并保存。因为每次相加都是原始序列中的数字值。接下来就是把所有数相等作为一个条件循环判断，不断累加最小值。最终回报是最小公倍数。七。表格推演计算表格的计算方法是将一组数除以最小的质数2，直到不能被2整除，再继续除以下一个质数3(剩余数中最小的质数)，直到所有数都是1。最后，所有有效的素数乘积都是最小公倍数。想想吧。如果让用代码实现，能活吗？

公共long lcm03(long...n){ Map & lt；Long，List & ltLong & gt& gtkeys = new HashMap & lt& gt();for (long key : n) { keys.put(key，new ArrayList & ltLong & gt(){ { add(key)；}});} system . out . print(& # 34；执行表格计算: r nx & # 34);长素性= 2，cachePrimality =素性，filterCount = 0，LCM = 1；//取所有元素的最后一位为1作为条件while (filterCount！= keys . size()){ int refresh = 0；filter count = 0；对于(图。Entry & ltLong，List & ltLong & gt& gtentry:keys . entry set()){ long value = entry . getvalue()。get(entry.getValue()。size()-1)；if(value = = 1){ filter count++；}//可分处理if(value % primitive ness = = 0){ entry . getvalue()。add(价值/原始)；刷新++；} else { entry.getValue()。添加(值)；} }//刷新除数if (refresh = = 0) {for (map。词条；素性||(值& ltcachePrimality & & value & gtprimality)){ cachePrimality = value；} entry.getValue()。移除(entry.getValue()。size()-1)；} primality = cachePrimality} else {//累计产品LCM * = cacheproductivitysystem . out . print(cachePrimality+& # 34；");} } keys.forEach((key，values)-& gt；{ system . out . println()；for(long v:values){ system . out . print(v+ & # 34；");} });system . out . println(& # 34； r n & # 34);返回lcm在代码实现中，我们使用Map作为表的键，并在Map中列出表中每一行的数据。通过这样的结构建立一个表格。接下来，所有元素的最后一位为1作为条件循环处理数据，前2作为素数整除表中的数据，保存在下一个数列中。当2不能被整除时，刷新质数，选择另一个列表中最小的质数作为除数继续。在这个过程中，有效素数的乘积会被累加，这个乘积的最终结果是最小公倍数。八、测试验证单元测试

@ test public void test _ euclidean(){ lastconmultiple lastconmultiple = new lastconmultiple()；//system . out . println(& # 34；最小公倍数:& # 34；+lastconmultiple . LCM 01(2，7))；system . out . println(& # 34；最小公倍数:& # 34；+lastconmultiple . LCM 02(3，4，6))；//system . out . println(& # 34；最小公倍数:& # 34；+lastconmultiple . LCM 03(3，4，6))；system . out . println(& # 34；最小公倍数:& # 34；+lastconmultiple . LCM 03(3，4，6，8))；//system . out . println(& # 34；最小公倍数:& # 34；+lastconmultiple . LCM 03(4，7，12，21，42))；}测试结果

执行累加计算：[3,4,6][6,4,6][6,8,6][9,8,6][9,8,12][9,12,12]最小公倍数：12执行表格计算：x 2 2 2 3 3 3 3 3 1 4 2 1 1 1 6 3 3 3 1 8 4 2 1 1 最小公倍数：24到这里测试就结束了，本章一共介绍了三种计算最小公倍数的方法。那如果只让你看到逻辑，你能写出最终的代码吗？九、常见面试最大公约数的使用用途？如何使用代码实现最大公约数计算？你是否了解欧几里德算法？关于数论你还记得多少？RSA 加密算法为什么需要用到公约数计算？如何计算两数的最小公倍数？如果计算多个整数的最小公倍数？你能说一下具体如何实现这种X的计算流程吗？你知道最小公倍数计算的用途吗？What is the most efficient way to calculate the least common multiple of two integers?：https://stackoverflow.com/questions/3154454/what-is-the-most-efficient-way-to-calculate-the-least-common-multiple-of-two-int/3154503#3154503Least common multiple：https://en.wikipedia.org/wiki/Least_common_multipleChebyshev function：https://en.wikipedia.org/wiki/Chebyshev_function欧几里德算法：https://en.wikipedia.org/wiki/Euclidean_algorithm线性组合：https://en.wikipedia.org/wiki/Linear_combination贝祖定理：https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity