Smallest Multiple Algorithm using Bruteforce or GCD/LCM

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?

Bruteforce Algorithm to Find the Least Common Multiples

The most intuitive solution is to check number one by one and then test if it can be divisible by all the numbers from 1 to 20. A better solution is to skip 20 each time.

1
2
3
4
5
6
7
8
9
10
11
12

function checkDivision(n) {
    if (n == 0) return false;
    for (let i = 2; i <= 20; ++ i) {
        if (n % i != 0) return false;
    }
    return true;
}
 
let i = 0;
while (!checkDivision(i)) {
    i += 20;
}

function checkDivision(n) {
    if (n == 0) return false;
    for (let i = 2; i <= 20; ++ i) {
        if (n % i != 0) return false;
    }
    return true;
}

let i = 0;
while (!checkDivision(i)) {
    i += 20;
}

This takes pretty quickly to come up a solution which is 232792560

Greatest Common Divisor and Least Common Multiples

Another solution is to compute the Least Common Multiples of the numbers between 1 to 20. To compute the LCM of two numbers a, b, we need to compute the Greatest Common Divisor or both numbers.

.

We can use the iterative approach to compute the GCD.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function gcd(a, b) {
    while (b != 0) {
        let c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 
function lcm(a, b) {
    return a * b / gcd(a, b);
}
 
let res = 1;
for (let i = 1; i <= 20; ++ i) {
    res = lcm(res, i);
}
 
console.log(res);

function gcd(a, b) {
    while (b != 0) {
        let c = a % b;
        a = b;
        b = c;
    }
    return a;
}

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

let res = 1;
for (let i = 1; i <= 20; ++ i) {
    res = lcm(res, i);
}

console.log(res);

–EOF (The Ultimate Computing & Technology Blog) —