一、前言
嘿，小傅哥怎么突然讲到大公约数了？
这么想你肯定是没有好好阅读前面章节中小傅哥讲到的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种计算方式，一种是循环另外一种是递归。—— 方便很多看不懂递归的小伙伴可以用另外的方式学习。
1. 循环实现
public long gcd01(long m, long n) {
m = Math.abs(m);
n = Math.abs(n);
while (m != && n != && m != n) {
if (m > n) {
m = m - n;
} else {
n = n - m;
}
}
return m == ? n : m;
}
- 两数循环处理中，条件为
m != 0 && n != 0 && m != n直至循环结束。
2. 递归实现
public long gcd02(long m, long n) {
if (m < n) {
long k = m;
m = n;
n = k;
}
if (m % n != ) {
long temp = m % n;
return gcd02(n, temp);
} else {
return n;
}
}
- 计算方式逻辑和条件是一样的，只不过这个是使用了递归调用的方式进行处理。
3. 测试验证
@Test
public void test_euclidean() {
Euclidean euclidean = new Euclidean();
System.out.println(euclidean.gcd01(124, 20));
System.out.println(euclidean.gcd02(124, 20));
}
测试结果
4
4
Process finished with exit code
- 计算 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 == ) || (n == )) ? : 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
while (m != && n != && m != n) {
if (m > n) {
m = m - n;
} else {
n = n - m;
}
}
return m == ? n : m;
}
- 首先这里是一个比较简单的方式，基于两数乘积除以大公约数，得到的结果就是小公倍数。
六、简单累加计算
此计算方式为，在一组正整数数列中，通过找到小的数字进行自身累加循环，直至所有数字相同时，则这个数字为小公倍数。—— 你能代码实现一下吗？
public long lcm02(long... n) {
long[] cache = n.clone();
// 以所有数字都相等作为条件
while (!isEquals(n)) {
System.out.println(JSON.toJSONString(n));
long min = n[];
int idx = ;
for (int i = ; i < n.length; i++) {
if (min > n[i]) {
min = n[i];
idx = i;
}
}
n[idx] = cache[idx] + min;
}
return n[];
}
- 在代码实现中，首先要把n个整数数列进行克隆保存。因为每次相加的都是初的这个数列里的数字值。接下来就是以所有数字都相等作为条件循环判断，不断地的累加小的数值即可。终返回的就是小公倍数。
七、表格推演计算
表格计算方式为将一组数字以小的质数2开始整除，直到不能被2整除后，用下一个质数3继续整除（剩余的数字中比大的小的质数）直至所有数字都为1的时候结束。终所有有效的质数乘积就是小公倍数。—— 想想如果这让你用代码实现，你能肝出来吗？
public long lcm03(long... n) {
Map<Long, List<Long>> keys = new HashMap<>();
for (long key : n) {
keys.put(key, new ArrayList<Long>() {{
add(key);
}});
}
System.out.print("执行表格计算：\r\nx ");
long primality = 2, cachePrimality = primality, filterCount = , lcm = 1;
// 以所有元素后一位为1作为条件
while (filterCount != keys.size()) {
int refresh = ;
filterCount = ;
for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
long value = entry.getValue().get(entry.getValue().size() - 1);
if (value == 1) {
filterCount++;
}
// 整除处理
if (value % primality == ) {
entry.getValue().add(value / primality);
refresh++;
} else {
entry.getValue().add(value);
}
}
// 刷新除数
if (refresh == ) {
for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
long value = entry.getValue().get(entry.getValue().size() - 1);
// 找到下一个符合的素数
if (value > primality || (value < cachePrimality && value > primality)) {
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 (long v : values) {
System.out.print(v + " ");
}
});
System.out.println("\r\n");
return lcm;
}
- 在代码实现中我们通过 Map 作为表的key，Map 中的 List 作为表每一行数据。通过这样一个结构构建出一张表。
- 接下来以所有元素后一位为1作为条件循环处理数据，用开始的2作为素数整除列表中的数据，并保存到下一组数列中。当2不能整除时，则刷新素数，选取另外一个列表中小的素数作为除数继续。
- 这个过程中会累计有效素数的乘积，这个乘积的终结果就是小公倍数。
八、测试验证
单元测试
@Test
public void test_euclidean() {
LastCommonMultiple lastCommonMultiple = new LastCommonMultiple();
// 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
执行表格计算：
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#3154503
- Least common multiple：https://en.wikipedia.org/wiki/Least_common_multiple
- Chebyshev 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
