Smallest Common Multiple Divisible by

Question

I'm working in JavaScript and I am solving for smallest common multiple, for two numbers, and the smallest common multiple has to be divisible by all numbers between the two numbers.

Right now, my code is not working at all and nothing is being returned. I had one function to calculate the smallest common multiple and a second function to determine if that multiple was divisible by the numbers between the smallest and largest number.

function smallestCommons(arr) {

    var max = 0;
    var min = 0;
    var lcm = 0;
    var max2 = 0;
       if(arr[0]> arr[1]) {
         max = arr[0];
         min = arr[1];
       } else {
         max = arr[1];
         min = arr[0];
       }

       function range(item){
         for(var j = min+1; j < max; j++){
           if(item % j !== 0){
             return 0;
           } else {
             return item;
           }
         }
       }   
       function lcmFind(min1, max1){
         for(var i =1; i < min1; i++){
             max1 = max1 * i;

             if(range(max1) === 0){
               continue;
             } else {
               return range(max1);
             }       
           }  
         }         
       return lcmFind(min,max);    
     }
     smallestCommons([1,5]);

Answer 1

You are looking for lcm, or least common multiple. It so happens that lcm(a, b) = a * b / gcd(a, b) where gcd is greatest common divisor, the largest number that both numbers are a multiple of. There is an algorithm called the Euclidean Algorithm for quickly calculating gcd: gcd(a, b) = gcd(b, a % b) where a%b is a modulo b. In javascript, it is this.

function gcd(a, b) {
    if (b === 0) {
        return a; // so that the recursion does not go on forever
    } else {
        return gcd(b, a % b);
    }
}

Then, you can define lcm like this.

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

EDIT: In order to calculate the lcm of a list of numbers, just reduce with the lcm function. So in order to calculate the lcm of all numbers in a range, this code will work. (assuming the range is inclusive for the 2 arguments)

function lcmOfRange(a, b) {
    let range = [];
    for (let i = a; i <= b; i++) {
        range.push(i);
    }
    return lcmOfList(range);
}

function lcmOfList(arr) {
    return arr.reduce(lcm);
}

This is equivalent to

function lcmOfRange(a, b) {
    let result = a;
    for (let i = a + 1; i <= b; i++) {
        result = lcm(result, i);
    }
    return result;
}