关于java:这个彬彬就是逊啦才搞懂小学知识求最小公倍数

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)$

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

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

更相减损法

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

算法步骤是这样的：

1. 先判断两数是否为偶数，是偶数则用 2 先进行约简，直到两数其中之一不为偶数
2. 以较大的数减较小的数，接着把所得的差与较小的数比拟，并以大数减小数。持续这个操作，直到所得的减数和差相等为止。
3. 将第一步中约掉的若干个 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);
        }
    }
}

最初的最初

由自己程度所限，不免有谬误以及不足之处，屏幕前的靓仔靓女们 如有发现，恳请指出！

最初，谢谢你看到这里，谢谢你认真对待我的致力，心愿这篇博客对你有所帮忙！

你轻轻地点了个赞，那将在我的心里世界削减一颗亮堂而夺目的星！