ASCII码 ASCII码

这个彬彬就是逊啦—才搞懂小学知识求最小公倍数

发布于：2022-06-27 11:54:18  栏目：技术文档

前言这个彬彬就是逊啦，不会求两个整数的最小公倍数，不过没事啦，我超勇的啦，我来帮彬彬求解！

下面进入紧张刺激的环节，看题时间到！不妨来看看这个困扰彬彬的题，请往下看啦！

题目正整数 a 和正整数 b 的最小公倍数是指 能被 a 和 b 整除的最小的正整数值

设计一个算法，求输入 a 和 b 的最小公倍数。

数据范围：$1 \le a,b \le 100000 $

输入描述：

输入两个正整数A和B。

输出描述：

输出A和B的最小公倍数。

示例1

  1. 输入：
  2. 5 7
  3. 输出：
  4. 35

前置知识如果你熟悉最小公倍数、最大公约数、倍数、约数、整除、除以、除，这些概念，这部分的内容可以直接跳过啦。

Least Common Multiple：最小公倍数

两个整数 或者 多个整数，共同拥有的倍数，就是公倍数，除了 0 以外，最小的共有的倍数称为「最小公倍数」。

整数 a , b 的最小公倍数记为：[a, b]整数 a , b , c 的最小公倍数记为：[a, b, c]以此类推。

另一个概念：最大公约数（最大公因数）Greatest Common Divisor

两个整数 或者 多个整数，共同拥有的约数，就是公约数，其中最大的约数就是「最大公约数」。

整数 a , b 的最大公约数记为：(a, b)整数 a , b , c 的最大公约数记为：(a, b, c)倍数 和 约数 的概念

如果数 a 能被数 b 整除，则 a 就叫做 b 的「倍数」，b 就叫做 a 的「约数」。

约数和倍数都表示一个整数与另一个整数的关系，是不能单独存在的。

需要注意「倍」和「倍数」是不同的意思！

整除的概念

整数 a 除以整数 b，即 a ÷ b，商为整数，且余数为 0，其中 a 称为「被除数」，b 称为「除数」，记为 b|a（其中符号 | 是整除的意思），读作 b 能整除 a，a 能被 b 整除。b 称为 a 的约数，a 称为 b 的倍数。

我这里举几个例子：

$12 ÷ 4 = 3$

读作 12 除以(divide by) 4，或者 4 除(divide) 12，可以理解成用 4 去拆分 12，可以分成 3 份。

12 为被除数，4 为除数，3 为商4 是 12 的约数， 12 是 4 的倍数同理

$12 ÷ 2 = 6$

读作 12 除以 2，可以理解用2去拆分12，可以分成6份

12 为被除数，2 为除数，6为商2 是 12 的约数， 12 是 2 的倍数同理

$12 ÷ 1 = 12$

读作 12 除以 1，可以理解成用1去拆分12，可以分成12份

12 为被除数，1 为除数，12为商1 是 12 的约数， 12 是 1 的倍数再来看看这个例子：

$16 ÷ 4 = 4$

16 是被除数，4 是除数，商为44 是 16 的约数，16 是 4 的倍数$16 ÷ 2 = 8$

2 是 16 的约数，16 是 2 的倍数$16 ÷ 1 = 16$

1 是 16 的约数，16 是 1 的倍数从上面我们可以发现 12 和 16 的共同拥有的约数是 1，2，4，其中最大的约数是 4。

所以记 12 和 16 的最大公约数为：(12, 16) = 4

4 的倍数有 4 8 12 16 24 …

6 的倍数有 6 12 18 24 …

4 和 6 共同拥有的倍数是 12 24 …，其中最小的倍数是12

所以记4和6的最小公倍数为：[4, 6] = 12

这样一梳理，是不是通透了许多~（不通透当我没说）

解题思路最小公倍数和最大公约数有这样的定理：$(a, b) × [a, b] = a × b$

即 这两数的最小公倍数 × 这两数的最大公约数 = 这两数相乘

所以，我们想求两个数的最小公倍数，就可以先求出这两数的最大公约数，进而求出这两数的最小公倍数

通过 这两数相乘 ÷ 这两个数的最大公约数 = 最小公倍数 进行求解。

即 $[a, b] = a × b ÷ (a, b)$

那么问题来了，如何求最大公约数呢？？

有好几种方法，比如短除法、辗转相除法、更相减损法，这里先用更相减损法。

更相减损法更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。算法步骤是这样的：

先判断两数是否为偶数，是偶数则用 2 先进行约简，直到两数其中之一不为偶数以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。将第一步中约掉的若干个 2 与第二步中等数的乘积就是所求的最大公约数。那么我们就按这个步骤来写求两个数的最大公约数的代码：

  1. public static int getGreatestCommonDivisor(int a, int b) {
  2.         // 记录两数是偶数时，约掉2的次数
  3.         int cnt = 0;
  4.         // 记录最大公约数
  5.         int ans = 1;
  6.         // 判断两数是否为偶数，是偶数则用2先进行约简
  7.         while ((a & 1) == 0 && (b & 1) == 0) {
  8.             a >>= 1;
  9.             b >>= 1;
  10.             ++cnt;
  11.         }
  12.         // 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。
  13.         // 继续这个操作，直到所得的减数和差相等为止。
  14.         while (a != b) {
  15.             if (a > b) {
  16.                 a -= b;
  17.             } else {
  18.                 b -= a;
  19.             }
  20.         }
  21.         // 计算得最大公约数
  22.         if (cnt != 0) {
  23.             ans = a * (cnt << 1);
  24.         } else {
  25.             ans = a;
  26.         }
  27.         return ans;
  28.     }

代码

  1. public class Main {
  3.     public static int getGreatestCommonDivisor(int a, int b) {
  4.         // 记录两数是偶数时，约掉2的次数
  5.         int cnt = 0;
  6.         // 记录最大公约数
  7.         int ans = 1;
  8.         // 判断两数是否为偶数，是偶数则用2先进行约简
  9.         while ((a & 1) == 0 && (b & 1) == 0) {
  10.             a >>= 1;
  11.             b >>= 1;
  12.             ++cnt;
  13.         }
  14.         // 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。
  15.         // 继续这个操作，直到所得的减数和差相等为止。
  16.         while (a != b) {
  17.             if (a > b) {
  18.                 a -= b;
  19.             } else {
  20.                 b -= a;
  21.             }
  22.         }
  23.         // 计算得最大公约数
  24.         if (cnt != 0) {
  25.             ans = a * (cnt << 1);
  26.         } else {
  27.             ans = a;
  28.         }
  29.         return ans;
  30.     }
  32.     public static void main(String[] args) {
  33.         Scanner in = new Scanner(System.in);
  34.         while (in.hasNext()) {
  35.             int a = in.nextInt();
  36.             int b = in.nextInt();
  37.             int lcm = (a * b) / getGreatestCommonDivisor(a, b);
  38.             System.out.println(lcm);
  39.         }
  40.     }
  41. }

由本人水平所限，难免有错误以及不足之处， 屏幕前的靓仔靓女们 如有发现，恳请指出！

最后，谢谢你看到这里，谢谢你认真对待我的努力，希望这篇博客对你有所帮助！

你轻轻地点了个赞，那将在我的心里世界增添一颗明亮而耀眼的星！

相关推荐
阅读 +

© 2020 asciim码

人生就是一场修行