javascriptfunctionmathrecursion

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

Solution

  • 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