# Project Euler #5 – Smallest Multiple

Posted on

Problem

JavaScript is my first programming language, and I’m still pretty new. I’m just looking for feedback. What can I do to make this more efficient and handle larger numbers?

``````// Project Euler - Smallest Multiple
// This program finds the smallest positive number
// that is evenly divisible by all numbers between 1 and n.

function smallestMult(n){
var dividends = []; // the numbers by which the program must divide
for (var i = 1; i <= n; i ++){
dividends.push(i);
}
var result = n; // will increase in increments of n
var count = 0; //  result has been found when count == n
while (count < n){
for (var x = 0; x < dividends.length; x ++){
if (result % dividends[x] === 0){
count += 1; // increases count for every successful division
}
else {
count = 0; // if a division fails, count returns to 0
result += n; // and the result is increased by n
}
}
}
return result;
}
console.log(smallestMult(12));
``````

Solution

“Smallest Multiple” is, in other words, the least common multiple of a range of numbers. The function below implements the least common multiple, `lcm`:

``````var lcm = function (a, b) {
// lcm is defined as:
// lcm(a, b) = abs(a * b) / gcd(a, b)
if (isNumber(a) && isNumber(b)) {
if (!isInteger(a) || !isInteger(b)) {
throw new Error('Parameters in function lcm must be integer numbers');
}
return (Math.abs(a) / gcd(a, b)) * Math.abs(b);
}
};
``````

The helper functions `isNumber` and `isInteger` are as follows:

``````var isNumber = function(value) {
return (value instanceof Number) || (typeof value == 'number');
};

var isInteger = function(value) {
return (value === Math.round(value));
};
``````

Ok, so now we have to implement `gcd`, the greatest common divisor. Here we can use Euclidean Algorithm:

``````var gcd = function (a, b) {
if (isNumber(a) && isNumber(b)) {
if (!isInteger(a) || !isInteger(b)) {
throw new Error('Parameters in function gcd must be integer numbers');
}

// http://en.wikipedia.org/wiki/Euclidean_algorithm
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return (a < 0) ? -a : a;
}
};
``````

Now that we have `lcm`, we’ll use the fact that `lcm(a,b,c)``lcm(lcm(a,b),c)` to make the `smallestMultiple` function:

``````var smallestMultiple = function (endOfRange) {
if (isNumber(endOfRange)) {
if (endOfRange <= 0) {
throw new Error('Parameter in function smallestMultiple must be greater than zero');
}
if (!isInteger(endOfRange)) {
throw new Error('Parameter in function smallestMultiple must be a positive integer');
}
// Observing that lcm(a,b,c) ≡ lcm(lcm(a,b),c)
var a = 1;
for (var i = 1; i <= endOfRange; i++) {
a = lcm(a, i);
}
return a;
}
};
``````

The full code is as follows:

``````var isNumber = function(value) {
return (value instanceof Number) || (typeof value == 'number');
};

var isInteger = function(value) {
return (value === Math.round(value));
};

var gcd = function (a, b) {
if (isNumber(a) && isNumber(b)) {
if (!isInteger(a) || !isInteger(b)) {
throw new Error('Parameters in function gcd must be integer numbers');
}

// http://en.wikipedia.org/wiki/Euclidean_algorithm
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return (a < 0) ? -a : a;
}
};

var lcm = function (a, b) {
// lcm is defined as:
// lcm(a, b) = abs(a * b) / gcd(a, b)
if (isNumber(a) && isNumber(b)) {
if (!isInteger(a) || !isInteger(b)) {
throw new Error('Parameters in function lcm must be integer numbers');
}
return (Math.abs(a) / gcd(a, b)) * Math.abs(b);
}
};

var smallestMultiple = function (endOfRange) {
if (isNumber(endOfRange)) {
if (endOfRange <= 0) {
throw new Error('Parameter in function smallestMultiple must be greater than zero');
}
if (!isInteger(endOfRange)) {
throw new Error('Parameter in function smallestMultiple must be a positive integer');
}
// Observing that lcm(a,b,c) ≡ lcm(lcm(a,b),c)
var a = 1;
for (var i = 1; i <= endOfRange; i++) {
a = lcm(a, i);
}
return a;
}
};
``````

The main point of everything above is not to talk to you about efficiency of how to handle larger numbers, but it’s about something much more important, especially for beginners such as you and I: abstractions.

To abstract means to give names to things, so you can refer to them as a unit. For example, “stir”, “fry” and “boil” are abstractions. Which one is better: “stir for 10 minutes, fry the steak and boil the water” or “move the spoon inside the pot for 10 minutes, heat a little oil on a fridge and put the steak on it, and bring the water to a temperature of a 100 degrees Celsius”? Note that the former is more descriptive even though it’s less detailed. Similarly, defining `smallestMultiple` as the `lcm` of a range of numbers is more helpful than your ad hoc procedure. When you get a job as a programmer, remember that abstractions are king, and that premature optimizations are the root of all evil.

Also, sorry if the validations were excessive or unclear, as javascript is not my primary language and it’s combination of dynamic and weak typing makes me a little afraid of it.