共计 2608 个字符，预计需要花费 7 分钟才能阅读完成。
HJ108 求最小公倍数
前言
这个彬彬就是逊啦，不会求两个整数的最小公倍数，不过没事啦，我超勇的啦，我来帮彬彬求解！
上面进入缓和刺激的环节，看题工夫到！无妨来看看这个困扰彬彬的题，请往下看啦！
题目
正整数 a 和正整数 b 的最小公倍数是指 能被 a 和 b 整除的最小的正整数值
设计一个算法，求输出 a 和 b 的最小公倍数。
数据范畴：$1 \le a,b \le 100000 $
输出形容：
输出两个正整数 A 和 B。
输入形容：
输入 A 和 B 的最小公倍数。
示例 1
输出：5 7
输入：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 是除数，商为 4
- 4 是 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 与第二步中等数的乘积就是所求的最大公约数。
那么咱们就按这个步骤来写求两个数的最大公约数的代码：
public static int getGreatestCommonDivisor(int a, int b) {
// 记录两数是偶数时，约掉 2 的次数
int cnt = 0;
// 记录最大公约数
int ans = 1;
// 判断两数是否为偶数，是偶数则用 2 先进行约简
while ((a & 1) == 0 && (b & 1) == 0) {
a >>= 1;
b >>= 1;
++cnt;
}
// 以较大的数减较小的数，接着把所得的差与较小的数比拟，并以大数减小数。// 持续这个操作，直到所得的减数和差相等为止。while (a != b) {if (a > b) {a -= b;} else {b -= a;}
}
// 计算得最大公约数
if (cnt != 0) {ans = a * (cnt << 1);
} else {ans = a;}
return ans;
}代码
public class Main {public static int getGreatestCommonDivisor(int a, int b) {
// 记录两数是偶数时，约掉 2 的次数
int cnt = 0;
// 记录最大公约数
int ans = 1;
// 判断两数是否为偶数，是偶数则用 2 先进行约简
while ((a & 1) == 0 && (b & 1) == 0) {
a >>= 1;
b >>= 1;
++cnt;
}
// 以较大的数减较小的数，接着把所得的差与较小的数比拟，并以大数减小数。// 持续这个操作，直到所得的减数和差相等为止。while (a != b) {if (a > b) {a -= b;} else {b -= a;}
}
// 计算得最大公约数
if (cnt != 0) {ans = a * (cnt << 1);
} else {ans = a;}
return ans;
}
public static void main(String[] args) {Scanner in = new Scanner(System.in);
while (in.hasNext()) {int a = in.nextInt();
int b = in.nextInt();
int lcm = (a * b) / getGreatestCommonDivisor(a, b);
System.out.println(lcm);
}
}
}最初的最初
由自己程度所限，不免有谬误以及不足之处，屏幕前的靓仔靓女们 如有发现，恳请指出！
最初，谢谢你看到这里，谢谢你认真对待我的致力，心愿这篇博客对你有所帮忙！
你轻轻地点了个赞，那将在我的心里世界削减一颗亮堂而夺目的星！
