可被整除的最小公倍数

Question

我在 JavaScript 工作，正在求解两个数的最小公倍数，最小公倍数必须能被两个数之间的所有数整除。

现在，我的代码根本不起作用，也没有返回任何内容。我有一个函数用于计算最小公倍数，还有一个函数用于确定该倍数是否可以被最小数和最大数之间的数字整除。

function smallestCommons(arr) {

    var max = 0;
    var min = 0;
    var lcm = 0;
    var max2 = 0;
       if(arr[0]> arr[1]) {
         max = arr[0];
         min = arr[1];
       } else {
         max = arr[1];
         min = arr[0];
       }

       function range(item){
         for(var j = min+1; j < max; j++){
           if(item % j !== 0){
             return 0;
           } else {
             return item;
           }
         }
       }   
       function lcmFind(min1, max1){
         for(var i =1; i < min1; i++){
             max1 = max1 * i;

             if(range(max1) === 0){
               continue;
             } else {
               return range(max1);
             }       
           }  
         }         
       return lcmFind(min,max);    
     }
     smallestCommons([1,5]);

Answer 1

您正在寻找 lcm，或最小公倍数。碰巧 lcm(a, b) = a * b / gcd(a, b) 其中 gcd 是最大公约数，即两个数都是其倍数的最大数。有一种算法称为欧几里德算法，用于快速计算 gcd：gcd(a, b) = gcd(b, a % b) 其中 a%b 是 a modulo b。 javascript里面是这个

function gcd(a, b) {
    if (b === 0) {
        return a; // so that the recursion does not go on forever
    } else {
        return gcd(b, a % b);
    }
}

那么，你可以这样定义lcm。

function lcm(a, b) {
    return a * b / gcd(a, b);
}

编辑：为了计算数字列表的 lcm，只需使用 lcm 函数进行归约。因此，为了计算范围内所有数字的 lcm，此代码将起作用。（假设范围包含 2 个参数）

function lcmOfRange(a, b) {
    let range = [];
    for (let i = a; i <= b; i++) {
        range.push(i);
    }
    return lcmOfList(range);
}

function lcmOfList(arr) {
    return arr.reduce(lcm);
}

这相当于

function lcmOfRange(a, b) {
    let result = a;
    for (let i = a + 1; i <= b; i++) {
        result = lcm(result, i);
    }
    return result;
}

可被整除的最小公倍数

Smallest Common Multiple Divisible by

javascript

algorithm

lcm