Blogger Information
Blog 11
fans 0
comment 0
visits 7942
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
这个彬彬就是逊啦—才搞懂小学知识求最小公倍数
P粉934491362
Original
1076 people have browsed it

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

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

题目
正整数 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 是除数,商为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 与第二步中等数的乘积就是所求的最大公约数。
那么我们就按这个步骤来写求两个数的最大公约数的代码:

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

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

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

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

Statement of this Website
The copyright of this blog article belongs to the blogger. Please specify the address when reprinting! If there is any infringement or violation of the law, please contact admin@php.cn Report processing!
All comments Speak rationally on civilized internet, please comply with News Comment Service Agreement
0 comments