Project Euler: #5 - Smallest multiple

Problem

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?

Problem Description

The Problem is straightforward. The smallest number that is divisible by all the numbers from 1 to 10 is 2520.

We need to find the smallest positive number that is divisible by all the numbers from 1 to 20

Approach

To calculate, let's break down all the prime numbers between 2 and 20.

So we will have an array like [2, 3, 5, 7, 11, 13, 17, 19].

Then for each of these prime components, we need to find the maximum number of occurrences in each number. In other words, factorize each number from 2 to 20 and find the number of times a particular prime number occurs.

For example, 12 has 2 occurrence of prime number 2 and 1 occurrence of prime number 3. Below is a chart with the maximum occurrence for each number.

Then you raise each prime number to its maximum occurrence: 2^4, 3^2, 5^1, … and multiply the result: 16 * 9 * 5 * ...

In this calculation, we involve only prime numbers between 1 and 20 because the other numbers are eventually multiples of these prime numbers.

Solution

const findPrimeNumbers = (start, end) => {
    let primeArray = [];

    for (let i = start; i <= end; i++) {
        let isPrime = true;
        for (let j = 2; j <= Math.ceil(i / 2); j++) {
            if ((i % j) === 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime === true) {
            primeArray.push(i);
        }
    }
    return primeArray;
};

const findFactors = (number) => {
    var factorsArray = [];

    for (let i = 2; i <= number; i++) {
        while ((number % i) === 0) {
            factorsArray.push(i);
            number /= i;
        }
    }
    return factorsArray;
}

const smallestDivNumber = () => {
    const primeArr = findPrimeNumbers(2, 20);

    for (let i = 0; i < primeArr.length; i++) {
        let maxOccur = 0;
        for (let j = 2; j <= 20; j++) {
            if (!(primeArr[i] > j)) {
                const factArr = findFactors(j);
                let countOccur = factArr
                                    .filter(x => x === primeArr[i]).length;
                if (countOccur > maxOccurance) maxOccur = countOccur;
            }
        }
        if (maxOccur > 0) primeArr[i] = Math.pow(primeArr[i], maxOccur);
    }

    return primeArr.reduce((acc, val) => acc * val, 1);
}

console.time("Time");
console.log(smallestDivNumber());
console.timeEnd("Time");

You can find my solution on GitHub 05

If you have another or a better solution, please leave it in the comments below.

For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.

Thank you!

Project Euler: #5 - Smallest multiple

Comments

Project Euler: JS Solution Explained!

Project Euler: #6 - Sum square difference

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #6 - Sum square difference

More from this blog

Problem

Problem Description

Approach

Solution