7

JavaScript 求最小公倍数

 2 years ago
source link: https://knightyun.github.io/2019/09/03/js-lcm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

最小公倍数(Least Common Multiple)

最小公倍数是中学数学知识中的一个概念，具体定义可以 自行了解，这里只大致解释一下，通常几个正整数会存在许多个倍数，每个倍数除以这几个正整数后都没有余数，而这些倍数之中最小的一个则称为最小公倍数；

一般直接计算最小公倍数较为困难，因此需要用到一个计算公式，即两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积，所以知道两个数的最大公约数或者求最小公倍数，就可以求得另外一个，接下来先来实现最大公约数的求法；

最大公约数(Greatest Common Divisor)

这也是与最小公倍数相似的另一个概念，几个正整数之间一般存在多个约数，即这几个正整数除以这个约数后都没有余数，这些约数中最大的一个称为最大公约数；下面来实现求最大公约数的函数；

最大质因数法

思路很简单，即将两个数分别递减，获取能同时被二者除尽的最大的一个数，即最大公约数：

function getGcd(a, b) {
    for (let i = a; i > 0; i--) {
        for (let j = b; j > 0; j--) {
            if (a % i === 0 && b % j === 0 && i === j) {
                return j;
            }
        }
    }
}

辗转相除法

思路是用两个数中的最大项除以最小项，如果能除尽，那么最小项便是这两个数的最大公约数；不能除尽则用最大项除以最小项所得余数，与最小项再进行同样的递归操作，最后得到最大的约数，也就是所谓的辗转相除；

function getGcd(a, b) {
    let max = Math.max(a, b);
    let min = Math.min(a, b);
    if (max % min === 0) {
        return min;
    } else {
        return getGcd(max % min, min);
    }
}

求最小公倍数

有了求最大公约数的函数后，再来求最小公倍数就简单了：

function getLcm(a, b) {
    return a * b / getGcd(a, b);
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK