1.前言咦，傅哥怎么突然说最大公约数了？如果你这样想，那你肯定没看过上一章付哥说的RSA算法。对于用欧拉结果计算出来的质数公钥e，其实需要用滚动除法来计算最大公约数。不用担心，你写的所有代码都是数理逻辑的具体实现，无非是难度的不同而已。所以如果你真的想学好编程思维而不仅仅是CRUD，你必须在数据结构、算法逻辑等方面打好基础。2.既然都是短除法，你还记得如何计算最大的吗？公约数，死鬼？上面的方法是我们在学校学的。这种计算方法称为短除法。简除法：是算术中除法的一种算法，将除法转化为一系列运算。短除法是长除法的简化，里面用到了心算，所以短除法更适合除数较小的除法。对于大多数人来说，当除以12或更小的数时，可以使用记忆中的乘法表内容在心里进行短除法。还有一些人可以处理具有较大除数的短除法。——摘自维基百科3.欧几里德算法短除法可以解决计算最大公约数的问题，但是在编程中总是很别扭，无法一个一个地尝试和计算数字，看起来很烦人。其实除了短除法，还有一种求公约数的方法，叫做欧氏算法。欧氏算法：是计算两个整数（数）的最大公约数[GCD（GreatestCommonDivisor）]，即能将它们整除而无余数的最大数的有效方法。它以古希腊数学家欧几里得的名字命名，欧几里德在他的《几何原本》（约公元前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整除。4.欧氏算法=欧氏算法的代码实现：https://en.wikipedia.org/wiki/Euclidean_algorithm在方法的实现中，计算最大公约数的方式是使用一个数减去另一个数，直到两个数相同或者其中一个数为0，那么最后一个不为零的数就是这两个数的最大公约数。付哥这里提供了两种计算方式，一种是循环，一种是递归。——方便很多不懂递归的朋友换种方式学习。1.循环实现publiclonggcd01(longm,longn){m=Math.abs(m);n=Math.abs(n);while(m!=0&&n!=0&&m!=n){如果(m>n){m=m-n;}else{n=n-m;}}返回m==0？n:m;}在两个数的循环处理中，条件为m!=0&&n!=0&&m!=n直到循环结束。2.递归执行publiclonggcd02(longm,longn){if(mn){m=m-n;}else{n=n-m;}}返回m==0？n:m;}首先，这里介绍一个比较简单的方法，基于两个数的乘积除以最大公约数，得到的结果是最小公倍数。6、简单累加计算这种计算方法是在一串正整数中找出最小的数，进行自我累加循环，直到所有数都相同，则这个数就是最小公倍数。——能用代码实现吗？publiclonglcm02(long...n){long[]cache=n.clone();//条件是所有数字都相等while(!isEquals(n)){System.out.println(JSON.toJSONString(n));长最小值=n[0]；intidx=0;对于(inti=0;in[i]){min=n[i];idx=我;}}n[idx]=缓存[idx]+min;}returnn[0];}在代码实现中，首先要克隆并保存n个整型数组。因为每次相加都是原序列中的数字值。接下来就是以所有数作为条件循环判断，不断累加最小值。最后返回的是最小公倍数。7.表推演法表推法是用最小的质数2除一组数，直到不能被2整除，继续用下一个质数3（大于本数的最小质数）整除remainingnumbers)直到所有数都为1时结束。最后所有有效素数的乘积为最小公倍数。——想想如果能用代码实现，能不能搞出来？publiclonglcm03(long...n){Map>keys=newHashMap<>();对于（长键：n）{键。put(key,newArrayList(){{add(key);}});}System.out.print("执行表计算：\r\nx");longprimality=2,cachePrimality=primality,filterCount=0,lcm=1;//以所有元素的最后一位为1为条件while(filterCount!=keys.size()){intrefresh=0;过滤器计数=0；for(Map.Entry>entry:keys.entrySet()){longvalue=entry.getValue().get(entry.getValue().size()-1);如果（值==1）{filterCount++;}//整数除法处理if(value%primality==0){entry.getValue().add(value/primality);刷新++；}else{entry.getValue().add(value);}}//刷新除数if(refresh==0){for(Map.Entry>entry:keys.entrySet()){longvalue=entry.getValue().get(entry.getValue().size()-1);//寻找下一个符合A的素数if(value>primality||(valueprimality)){cachePrimality=value;}entry.getValue().remove(entry.getValue().size()-1);}primality=cachePrimality;}else{//累积乘积lcm*=cachePrimality;System.out.print(cachePrimality+"");}}keys.forEach((key,values)->{System.out.println();for(longv:values){System.out.print(v+"");}});System.out.println("\r\n");returnlcm;}在代码实现中，我们将Map作为一个表，将Map中的key和List作为一个表。每行数据通过这样的结构构成一张表。接下来循环处理数据，条件是所有元素的最后一位为1，列表中的数据能被前2整除为质数，存入下一组数组。当2不可整除时，刷新素数，选择另一个列表中最小的素数作为除数继续。在这个过程中，对有效质数的乘积进行累加，这个乘积的最终结果就是最小公倍数。八、测试验证单元测试@Testpublicvoidtest_euclidean(){LastCommonMultiplelastCommonMultiple=newLastCommonMultiple();//System.out.println("最小公倍数："+lastCommonMultiple.lcm01(2,7));System.out.println("最小公倍数："+lastCommonMultiple.lcm02(3,4,6));//System.out.println("最小公倍数："+lastCommonMultiple.lcm03(3,4,6));System.out.println("最小公倍数："+lastCommonMultiple.lcm03(3,4,6,8));//System.out.println("最小公倍数："+lastCommonMultiple.lcm03(4,7,12,21,42));}测试结果累加计算：[3,4,6][6,4,6][6,8,6][9,8,6][9,8,12][9,12,12]最小公倍数：12进行表计算：x222333331421116333184211最小公倍数：24测试到此结束。本章介绍三种计算最小公倍数的方法。那么如果你只看到逻辑，你能写出最终的代码吗？9、常见面试中最大公约数有什么用？如何用代码实现最大公约数的计算？你知道欧几里得算法吗？关于数论，你还记得多少？为什么RSA加密算法需要用公约数计算？如何计算两个数的最小公倍数？如何计算多个整数的最小公倍数？你能告诉我如何实现X的这个计算过程吗？你知道最小公倍数的计算是为了什么吗？计算两个整数的最小公倍数的最有效方法是什么？：https://stackoverflow.com/questions/3154454/what-is-the-most-efficient-way-to-calculate-the-least-common-multiple-of-two-int/3154503#3154503最小公倍数：https://en.wikipedia.org/wiki/Least_common_multipleChebyshev函数：https://en.wikipedia.org/wiki/Chebyshev_functionEuclidean算法：https://en.wikipedia.org/wiki/Euclidean_algorithm线性组合：https://en.wikipedia.org/wiki/Linear_combination贝祖定理：https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
