如何找到一系列数字的最小公倍数？

Question

如何找到一系列数字的最小公倍数？

30

给定一个由两个数字组成的数组，让它们定义一段数字范围。例如，[2,6] 表示范围为2、3、4、5、6。我想编写javascript代码来查找该范围的最小公倍数。我的下面的代码仅适用于小范围，不能处理像[1,13]（即范围1、2、3、4、5、6、7、8、9、10、11、12、13）这样的大范围，会导致堆栈溢出。如何高效地找到一段数字范围的最小公倍数？

function leastCommonMultiple(arr) {
    var minn, max;
    if ( arr[0] > arr[1] ) {
        minn = arr[1];
        max = arr[0];
    } else {
        minn = arr[0];
        max = arr[1];
    }
    function repeatRecurse(min, max, scm) {
        if ( scm % min === 0 && min < max ) {
            return repeatRecurse(min+1, max, scm);
        } else if ( scm % min !== 0 && min < max ) {
            return repeatRecurse(minn, max, scm+max);
        }
        return scm;
    } 
    return repeatRecurse(minn, max, max);
}

- john chau

我仍然不了解您提到的分治算法...是欧几里得算法吗？我没有时间学习欧几里得算法，但如果其他方法都失败了，我会使用欧几里得算法...我真的希望有人能够使用高阶函数和记忆化（var cache = {}）来解决这个问题，但我不认为这是可能的。 - john chau

1

@vinayakj - 分治算法利用递归 :) - rgbchris

@rgbchris 但在“分而治之”的递归中，递归不必在整个数据上进行，而是在子集上进行，因此您不会遇到堆栈溢出问题。 - vinayakj

我认为vinayakj的意思是尾递归优化？？？？分治法的最佳例子是归并排序。 - john chau

2

与多个数字的最小公倍数相关的内容非常简短而惊人：https://dev59.com/n6bja4cB1Zd3GeqPfmfH#49722579 - Avatar

显示剩余3条评论

30个回答

7

由于这个问题最近又被提出来了，我认为对于这个问题的简单解决方案是编写非常简单的帮助函数来计算两个整数的最大公因数（gcd），计算两个整数的最小公倍数（lcm），计算一组整数的最小公倍数（lcmAll），生成两个给定整数之间整数范围（rng），最后，在我们的主要函数中，计算两个给定整数之间整数范围的最小公倍数（lcmRng）：

const gcd = (a, b) => b == 0 ? a : gcd (b, a % b)
const lcm = (a, b) =>  a / gcd (a, b) * b
const lcmAll = (ns) => ns .reduce (lcm, 1)
const rng = (lo, hi) => [...Array (hi - lo + 1)] .map ((_, i) => lo + i)

const lcmRng = (lo, hi) => lcmAll (rng (lo, hi))

console .log (lcmRng (1, 13))

所有这些函数都很简单。虽然这个问题标记为递归，但只有gcd是递归的。如果这是一个尝试使用递归的尝试，我们可以采用类似下面这样的递归方式重写lcmAll:

const lcmAll = (ns) => 
  ns.length == 0 
    ? 1 
    : lcm(ns[0], lcmAll(ns .slice (1)))

虽然我很喜欢递归，但在这里我看不到选择递归版本而不是reduce的其他理由。在这种情况下，reduce更加简洁。

最后，如果你真的想要请求的API中，范围边界是以数组形式传递的，那么你可以再编写一个包装器：

const leastCommonMultiple = ([lo, hi]) => lcmRng (lo, hi)

leastCommonMultiple ([1, 13]) //=> 360360

- Scott Sauyet

1

递归真的很有趣。我喜欢这个 lcmAll = (x, ...more) => more.length ? lcm(x, lcmAll(...more)) : x。也许可以展示一下使用递归实现的 rng？ - Mulan

1

这更好了。当然，rng可以用简单的方式轻松完成：const rng = (lo, hi) => lo > hi ? [] : [lo, ...rng(lo + 1, hi)]。 - Scott Sauyet

6

function smallestCommons(arr) {
  var max = Math.max(...arr);
  var min = Math.min(...arr);
  var candidate = max;

  var smallestCommon = function(low, high) {
    // inner function to use 'high' variable
    function scm(l, h) {
      if (h % l === 0) {
        return h;
      } else {
        return scm(l, h + high);
      }
    }
    return scm(low, high);
  };

  for (var i = min; i <= max; i += 1) {
    candidate = smallestCommon(i, candidate);
  }

  return candidate;
}

smallestCommons([5, 1]); // should return 60
smallestCommons([1, 13]); // should return 360360
smallestCommons([23, 18]); //should return 6056820

- Brian

5

LCM function for a range [a, b]

// Euclid algorithm for Greates Common Divisor
function gcd(a, b)
{ 
 return !b ? a : gcd(b, a % b);
} 

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

// LCM of all numbers in the range of arr=[a, b] 
function range_lcm(arr)
{
 // Swap [big, small] to [small, big]
 if(arr[0] > arr[1]) (arr = [arr[1], arr[0]]);

 for(x = result = arr[0]; x <= arr[1]; x++) {
  result = lcm(x, result);
 }
 
 return result; 
}

alert(range_lcm([8, 5])); // Returns 840

- krmld

4

我发现其他答案在我试图用两个数字找出最佳方法时有些混乱，所以我在维基百科上找到了最优解。

https://en.wikipedia.org/wiki/Least_common_multiple#Calculation

找到两个数的最小公倍数的最有效方法是 (a * b) / greatestCommonDivisor(a, b);

要做到这一点，我们需要计算最大公约数。使用欧几里得算法是最有效的方法。

https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm

以下是仅针对两个数字计算的完整解决方案，以防其他人遇到此问题但只需要计算两个数字：

const leastCommonMultiple = (a, b) => (a * b) / greatestCommonDivisor(a, b);

const greatestCommonDivisor = (a, b) => {
  const remainder = a % b;
  if (remainder === 0) return b;
  return greatestCommonDivisor(b, remainder);
};

- Alex K

3

我的回答可能不如其他人的那么花哨，但我认为它很容易阅读。

function smallestCommons(arr) {
 //order our array so we know which number is smallest and which is largest
 var sortedArr = arr.sort(sortNumber),
 //the smallest common multiple that leaves no remainder when divided by all the numbers in the rang
 smallestCommon = 0,
 //smallest multiple will always be the largest number * 1;
 multiple = sortedArr[1];

 while(smallestCommon === 0) {
  //check all numbers in our range
  for(var i = sortedArr[0]; i <= sortedArr[1]; i++ ){
   if(multiple % i !== 0 ){
    //if we find even one value between our set that is not perfectly divisible, we can skip to the next multiple
    break;
   }

   //if we make it all the way to the last value (sortedArr[1]) then we know that this multiple was perfectly divisible into all values in the range
   if(i == sortedArr[1]){
    smallestCommon = multiple;
   }

  }

  //move to the next multiple, we can just add the highest number.
  multiple += sortedArr[1];
 }

 console.log(smallestCommon);
 return smallestCommon;
}

function sortNumber(a, b) {
    return a - b;
}


smallestCommons([1, 5]); // should return 60.
smallestCommons([5, 1]); // should return 60.
smallestCommons([1, 13]); // should return 360360.
smallestCommons([23, 18]); // should return 6056820.

编辑：将答案转换为代码片段。

- Bullyen

1

喜欢这个，但是开头的 .sort() 会按字母顺序排序：[5,10] 会被排序为 [10,5]。一个小故障，但值得修复。 - isacvale

很好的发现 @isacvale！我已经更新了排序，使用自定义函数进行数字排序。 - Bullyen

1

这是您原始方法的非递归版本。

function smallestCommons(arr) {
  // Sort the array
  arr = arr.sort(function (a, b) {return a - b}); // numeric comparison;
  var min = arr[0];
  var max = arr[1];

  var numbers = [];
  var count = 0;

  //Here push the range of values into an array
  for (var i = min; i <= max; i++) {
    numbers.push(i);
  }
  //Here freeze a multiple candidate starting from the biggest array value - call it j
  for (var j = max; j <= 1000000; j+=max) {

    //I increase the denominator from min to max
    for (var k = arr[0]; k <= arr[1]; k++) {

      if (j % k === 0) { // every time the modulus is 0 increase a counting 
        count++; // variable
      }
    }

    //If the counting variable equals the lenght of the range, this candidate is the least common value
    if (count === numbers.length) { 
      return j; 
    }
    else{
      count = 0; // set count to 0 in order to test another candidate
    }
  }
}

alert(smallestCommons([1, 5]));

- ggglni

1

嗨，我发现了这个页面，想分享我的解决方案 :)

function smallestCommons(arr) {
  var max = Math.max(arr[0], arr[1]),
      min = Math.min(arr[0], arr[1]),
      i = 1;
  while (true) {
    var count = 0;
    for (j = min; j < max; j++) {
      if (max * i % j !== 0) {
        break;
      }
      count++;
    }
    if (count === (max - min)) {
      alert(max * i);
      return max * i;
    }
    i++;
  }
}
smallestCommons([23, 18]);

- user1137342

0

function range(min, max) {
  var arr = [];
  for (var i = min; i <= max; i++) {
    arr.push(i);
  }
  return arr;
}

function gcd (x, y) {
  return (x % y === 0) ? y : gcd(y, x%y);
}

function lcm (x, y) {
  return (x * y) / gcd(x, y); 
}

function lcmForArr (min, max) {
  var arr = range(min, max);
  return arr.reduce(function(x, y) {
    return lcm(x, y); 
  });
}

range(10, 15); // [10, 11, 12, 13, 14, 15]
gcd(10, 15); // 5
lcm(10, 15); // 30
lcmForArr(10, 15); //60060

- devellopah

0

function smallestCommons(arr) {
  var sortedArr = arr.sort(); // sort array first
  var tempArr = []; // create an empty array to store the array range
  var a = sortedArr[0];
  var b = sortedArr[1];
  for(var i = a; i <= b; i++){
    tempArr.push(i);
  }
  // find the lcm of 2 nums using the Euclid's algorithm
  function gcd(a, b){
    while (b){
      var temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

  function lcm(a, b){
    return Math.abs((a * b) / gcd(a, b));
  }
  var lcmRange = tempArr.reduce(lcm);


  return lcmRange;
}

- Fadyboy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rgbchris · Accepted Answer

我认为这可以完成任务。

function leastCommonMultiple(min, max) {
    function range(min, max) {
        var arr = [];
        for (var i = min; i <= max; i++) {
            arr.push(i);
        }
        return arr;
    }

    function gcd(a, b) {
        return !b ? a : gcd(b, a % b);
    }

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

    var multiple = min;
    range(min, max).forEach(function(n) {
        multiple = lcm(multiple, n);
    });

    return multiple;
}

leastCommonMultiple(1, 13); // => 360360