How to find the least common multiple of a range o

Question

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?

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);
}

Answer 1

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

Answer 2

 function leastCommonMultiple(arr) {
    /*
      function range(min, max) {
        var arr = [];
       for (var i = min; i <= max; i++) {
        arr.push(i);
      }
       return arr;
    }
    */
    var min, range;
     range = arr;
    if(arr[0] > arr[1]){
       min = arr[1];
    }
    else{
       min = arr[0]
    }

    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.forEach(function(n) {
       multiple = lcm(multiple, n);
    });

   return multiple;
}

console.log( leastCommonMultiple([1, 13]) )

Answer 3

How about:

// Euclid Algorithm for the Greatest Common Denominator
function gcd(a, b) {
    return !b ? a : gcd(b, a % b);
  }
  // Euclid Algorithm for the Least Common Multiple

function lcm(a, b) {
    return a * (b / gcd(a, b));
  }
  // LCM of all numbers in the range of arr = [a, b];

function smallestCommons(arr) {
  var i, result;
  // large to small - small to large
  if (arr[0] > arr[1]) {
    arr.reverse();
  } // only happens once. Means that the order of the arr reversed.
  for (i = result = arr[0]; i <= arr[1]; i++) { // all numbers up to arr[1] are arr[0].
    result = lcm(i, result); // lcm() makes arr int an integer because of the arithmetic operator.
  }
  return result;
}
smallestCommons([5, 1]); // returns 60

Answer 4

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(),
	//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;
}


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.

Answer 5

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

Answer 6

    /*Function to calculate sequential numbers 
in the range between the arg values, both inclusive.*/
    function smallestCommons(arg1, arg2) {
     
       if(arg1>arg2) { // Swap arg1 and arg2 if arg1 is greater than arg2
          var temp = arg1;
          arg1 = arg2;
          arg2 =temp;
        }
      
      /*
      Helper function to calculate greatest common divisor (gcd)
      implementing Euclidean algorithm */
      function gcd(a, b) {
      	return b===0 ? a : gcd(b, a % b); 
       }
      
      /*
      Helper function to calculate lowest common multiple (lcm) 
of any two numbers using gcd function above */
       function lcm(a,b){
          return (a*b)/gcd(a,b);
         }
      
      var total = arg1; // copy min value
      for(var i=arg1;i<arg2;i++){
          total = lcm(total,i+1);
         }
      //return that total
      return total;
    }
    /*Yes, there are many solutions that can get the job done.
    Check this out, same approach but different view point.
    */
    console.log(smallestCommons(13,1)); //360360
                                                                    

                                                        
            
              

                查看更多
                
             

              0人赞

                                                     添加讨论(0)

                                                                                                            
                               举报