Problem 5

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

https://projecteuler.net/problem=5

Deduce

The smallest multiple of a group of numbers can be found by getting prime factors of the numbers and multiplying together each prime factor to its highest degree.

The smallest multiple, or lowest common multiple or lcm, of 2, 4, 6, 7, and 9 can be found by factoring each number:

$\begin{align*} 2 & : 1^1 \times 2^1 \\ 4 & : 1^1 \times 2^2 \\ 6 & : 1^1 \times 2^1 \times 3^1 \\ 7 & : 1^1 \times 7^1 \\ 9 & : 1^1 \times 3^2 \end{align*}$

For this group of numbers there are 4 unique prime factors.

$\begin{align*} \text {FACTORS} & : \text {DEGREES} \\ 1 & : 1 \\ 2 & : 1, 2 \\ 3 & : 1, 2 \\ 7 & : 1 \end{align*}$

The lcm for $\{2, 4, 6, 7, 9\}$ is $1^1 \times 2^2 \times 3^2 \times 7^1 = 252$ .

We will reuse our primes generator from problem 3.

Factors

var Factor = (function(n) {
  function factor(n) {
    var primes = Primes.primesTo(Math.floor(Math.sqrt(n))),
        factors = Object.create(null),
        i = primes.length;
    factors[1] = 1;
    while(i--) {
      var counter = 0, prime = primes[i];
      while (n % prime === 0) {
        counter++;
        n = n / prime;
      }
      if (counter > 0) factors[prime] = counter;
    }
    factors[n] = 1;
    return factors;
  }

  return {
    factor: factor
  }
})();

Factor.factor(3);
// Object {1: 1, 3: 1}

Factor.factor(6);
// Object {1: 1, 2: 1, 3: 1}

Least Common Multiple

/**
 * Creates an array of positive numbers progressing from `start` to `end` inclusive.
 *
 * @param {number} start The start of the range.
 * @param {number} end The end of the range.
 * @returns {Array} Returns the new array of numbers.
 */
function range(start, end) {
  var c = end - start + 1,
      arr = Array(c);
  while ( c-- ) {
    arr[c] = end--
  }
  return arr;
}

function lcm(ns) {
  var common = Object.create(null),
      lcm = 1,
      factors = ns.map(function(n) { return Factor.factor(n); });

  // For each numbers' factors add and update if degree is higher than current.
  for (var i = 0, len = factors.length; i < len; i++) {
    for (var factor in factors[i]) {
      var degree = factors[i][factor];
      if (!common[factor] || common[factor] < degree) {
        common[factor] = degree;
      }
    }
  }
  // Multiply each factors to the power of degree.
  for (var factor in common) {
    lcm *= Math.pow(factor, common[factor]);
  }
  return lcm;
}
timer(lcm, 1, range(1, 10));
// lcm x 1: 0.069ms
// 2520

function euler5() {
  return lcm(range(1,20));
}
timer(euler5);
// euler5 x 1: 0.111ms
// 232792560