Javascript 如何找到一系列数字的最小公倍数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31302054/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find the least common multiple of a range of numbers?
提问by john chau
Given an array of two numbers, let them define the start and end of a range of numbers. For example, [2,6]means the range 2,3,4,5,6. I want to write javascript code to find the least common multiple for the range. My code below works for small ranges only, not something like [1,13](which is the range 1,2,3,4,5,6,7,8,9,10,11,12,13), which causes a stack overflow. How can I efficiently find the least common multiple of a range?
给定一个包含两个数字的数组，让它们定义一系列数字的开始和结束。例如，[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);
}
回答by rgbchris
I think this gets the job done.
我认为这可以完成工作。
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
回答by Brian
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
回答by Bullyen
Mine is not as fancy as the other answers but I think it is easy to read.
我的不像其他答案那么花哨，但我认为它很容易阅读。
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.Edit: Turned answer into snippet.
编辑：将答案变成片段。
回答by krmld
LCM function for a range [a, b]
范围 [a, b] 的 LCM 函数
// 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回答by Giorgio Giuliani
This is a non-recursive version of your original approach.
这是原始方法的非递归版本。
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]));回答by user1137342
Hey I came across this page and wanted to share my solution :)
嘿，我遇到了这个页面，想分享我的解决方案:)
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]);回答by Scott Sauyet
As this question has recently been revived, here's what I think is a simpler take on the question, writing very simple helper functions to calculate the greatest common divisor of two integers (gcd), to calculate the least common multiple of two integers (lcm), to calculate the least common multiple of an array of integers (lcmAll), to generate the range of integers between two given integers (rng), and finally, in our main function, to calculate the least common multiple of the range of integers between two given integers (lcmRng):
由于这个问题最近被复活了，我认为这是对这个问题的一个更简单的理解，编写非常简单的辅助函数来计算两个整数的最大公约数 ( 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))All of these functions are simple. Although the question was tagged recursion, only gcdis recursive. If this is an attempt to play with recursion, we could rewrite lcmAllin a recursive manner with something like this:
所有这些功能都很简单。虽然问题被标记为recursion，但只是gcd递归的。如果这是尝试使用递归，我们可以lcmAll以递归方式重写，如下所示：
const lcmAll = (ns) =>
ns.length == 0
? 1
: lcm(ns[0], lcmAll(ns .slice (1)))
Although I'm a big fan of recursion, I see no other reason to choose the recursive version here over the reduceone. In this case, reduceis cleaner.
尽管我是递归的忠实粉丝，但我认为没有其他理由在这里选择递归版本而不是递归版本reduce。在这种情况下，reduce更干净。
And finally, if you really want the API originally requested where the range bounds are passed in an array, you could write one more wrapper:
最后，如果您真的希望最初请求的 API 是在数组中传递范围界限的地方，您可以再编写一个包装器：
const leastCommonMultiple = ([lo, hi]) => lcmRng (lo, hi)
leastCommonMultiple ([1, 13]) //=> 360360
回答by Atanas Dachenski
Here is another nonrecursive for-loop solution
这是另一个非递归 for 循环解决方案
function smallestCommons(arr) {
var biggestNum = arr[0];
var smallestNum = arr[1];
var thirdNum;
//make sure biggestNum is always the largest
if (biggestNum < smallestNum) {
thirdNum = biggestNum;
biggestNum = smallestNum;
smallestNum = thirdNum;
}
var arrNum = [];
var count = 0;
var y = biggestNum;
// making array with all the numbers fom smallest to biggest
for (var i = smallestNum; i <= biggestNum; i += 1) {
arrNum.push(i);
}
for (var z = 0; z <= arrNum.length; z += 1) {
//noprotect
for (y; y < 10000000; y += 1) {
if (y % arrNum[z] === 0) {
count += 1;
break;
}
else if (count === arrNum.length) {
console.log(y);
return y;
}
else {
count = 0;
z = 0;
}
}
}
}
smallestCommons([23, 18]);
回答by sawan nirala
My solution using es6 feature is
我使用 es6 功能的解决方案是
Lcm of given numbers
给定数字的 Lcm
const gcd = (a, b) => (!b ? a : gcd(b, a % b));
const lcm = (a, b) => a * (b / gcd(a, b));
const getLcm = (arr) => {
const numbers = arr.sort((a, b) => parseInt(a) - parseInt(b));
let result = parseInt(numbers[0]);
for (let i = 1; i < numbers.length; i++) {
result = lcm(parseInt(result), parseInt(numbers[i + 1]));
}
return result;
};
Hcf of given numbers
给定数字的 Hcf
const getHcf = (arr) => {
const numbers = arr.sort((a, b) => parseInt(a) - parseInt(b));
let result = parseInt(numbers[0]);
for (let i = 1; i < numbers.length; i++) {
result = gcd(parseInt(numbers[i]), parseInt(result));
}
return result;
};
Call like this
像这样打电话
console.log(getLcm([20, 15, 10, 40])). Answer 120
console.log(getHcf([2, 4, 6, 8, 16])). Answer 2
回答by devellopah
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
