Smallest Common Multiple - how fast?

JavaScript
1

Hello guys,

what do you think about this cheesy solution to the problem in algorithms, to find the smallest common multiple? It really struggles with numbers that are greater than 20.

function smallestCommons(arr) {
  const myArr = arr.sort((x, y) => x - y);
  const rangeOfNums = [];
  for (let i = myArr[0]; i <= myArr[1]; i++) { rangeOfNums.push(i) };

  for (let i = 1; true; i++) {
    if (rangeOfNums.every(x => i % x == 0)) {
      return i;
    }
  }
}
console.log(smallestCommons([1, 20]));
2

To get a truly fast solution, you need to use some math.

Wikipedia has some nice articles on calculating the LCM of multiple numbers, on calculating the LCM quickly if you know the GCD, and quickly calculating the GCD of two numbers.

With there three ingredients, you can avoid slow loops with thousands of iterations and instead compute the smallest common multiple directly.

1 Like