乐趣区

关于后端:stackoverflow-提问计算两个整数的最小公倍数的最有效方法是什么

jiezi

作者：小傅哥
博客：https://bugstack.cn
源码：https://github.com/fuzhengwei…

积淀、分享、成长，让本人和别人都能有所播种！😄

一、前言

嘿，小傅哥怎么忽然讲到最大公约数了？

这么想你必定是没有好好浏览后面章节中小傅哥讲到的 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…

在辗转相除法的实现中，计算最大公约数的形式，就是应用一个数字减去另外一个数字，直到两个数字雷同或者有其中一个数字为 0，那么最初不为零的那个数字就是两数的最大公约数。

小傅哥在这里提供了 2 种计算形式，一种是循环另外一种是递归。—— 不便很多看不懂递归的小伙伴能够用另外的形式学习。

1. 循环实现

public long gcd01(long m, long n) {m = Math.abs(m);
    n = Math.abs(n);
    
    while (m != 0 && n != 0 && m != n) {if (m > n) {m = m - n;} else {n = n - m;}
    }
    return m == 0 ? 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 != 0) {
        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 0
  • 计算 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
    while (m != 0 && n != 0 && m != n) {if (m > n) {m = m - n;} else {n = n - m;}
    }
    return m == 0 ? n : m;
}
  • 首先这里是一个比较简单的形式，基于两数乘积除以最大公约数，失去的后果就是最小公倍数。

六、简略累加计算

此计算形式为，在一组正整数数列中，通过找到最小的数字进行本身累加循环，直至所有数字雷同时，则这个数字为最小公倍数。—— 你能代码实现一下吗？

public long lcm02(long... n) {long[] cache = n.clone();
    // 以所有数字都相等作为条件
    while (!isEquals(n)) {System.out.println(JSON.toJSONString(n));
        long min = n[0];
        int idx = 0;
        for (int i = 0; i < n.length; i++) {if (min > n[i]) {min = n[i];
                idx = i;
            }
        }
        n[idx] = cache[idx] + min;
    }
    return n[0];
}
  • 在代码实现中，首先要把 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 = 0, lcm = 1;
    // 以所有元素最初一位为 1 作为条件
    while (filterCount != keys.size()) {
        int refresh = 0;
        filterCount = 0;
        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 == 0) {entry.getValue().add(value / primality);
                refresh++;
            } else {entry.getValue().add(value);
            }
        }
        // 刷新除数
        if (refresh == 0) {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/que…
  • Least common multiple：https://en.wikipedia.org/wiki…
  • Chebyshev function：https://en.wikipedia.org/wiki…
  • 欧几里德算法：https://en.wikipedia.org/wiki…
  • 线性组合：https://en.wikipedia.org/wiki…
  • 贝祖定理：https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
退出移动版