Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find the least common multiple of a range of numbers?

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); } 
like image 435
john chau Avatar asked Jul 08 '15 19:07

john chau


People also ask

What are the 3 methods to find LCM?

There are three major methods to find the LCM of numbers, such as: Listing the multiples of the given numbers, prime factorisation of numbers and by division method.


1 Answers

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 
like image 130
rgbchris Avatar answered Oct 14 '22 10:10

rgbchris