HJ108 求最小公倍数

描述

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

输入描述：

输入两个正整数A和B。

输出描述：

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

示例1

输入：
5 7

输出：
35

示例2

输入：
2 4

输出：
4

解答

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let line;
    let num1;
    let num2;
    while ((line = await readline())) {
        let tokens = line.split(" ");
        num1 = parseInt(tokens[0]);
        num2 = parseInt(tokens[1]);
    }

    console.log(getLcm(num1, num2));
})();

function getGcd(num1, num2) {
    // 如果 num1 < num2，则交换两数
    if (num1 < num2) {
        [num1, num2] = [num2, num1];
    }

    let remainder;

    while (true) {
        remainder = num1 % num2;

        if (remainder === 0) {
            return num2;
        }

        num1 = num2;
        num2 = remainder;
    }

    return 1;
}

function getLcm(num1, num2) {
    const gcd = getGcd(num1, num2);

    const lcm = (num1 * num2) / gcd;

    return lcm;
}

知识点

求两数最大公约数：(GCD, greatest common divisor)

1. 被除数 / 除数，得到余数
2. 如果余数为 0，则除数为最小公约数
3. 如果余数不为 0，则 除数赋值给 被除数， 余数赋值给 除数，进行第 1 步

如， 64 和 18：

64 % 18 === 10

18 % 10 === 8

10 % 8 === 2

8 % 2 === 0     , 则 2 为最小公约数

求两数最小公倍数：(LCM, least common multiple)

最大公约数 × 最小公倍数 = 两数之积

参考

• 求最小公倍数的两种算法（最大公约数的三种算法） (opens new window)