Problem 5: Smallest multiple
is the smallest number that can be divided by each of the numbers from to without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from to ?
How to Solve
We’re looking for the least common multiple of numbers 1 through n. The relationship between GCD and LCM is expressed as:
Here, the greatest common divisor is computed efficiently using:
By applying this recursively, we can determine the of any two numbers quickly. Then, we combine them iteratively to find the overall — the smallest number evenly divisible by all integers from 1 to n.
Code Solution
function gcd(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function smallestMult(n) {
let a = 1;
for (let b = 2; b <= n; b++) {
a = (a * b) / gcd(a, b);
}
return a;
}