# 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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1672415507609/7ff88537-1091-4e9f-9246-476d117fe37d.png align="center")

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**

```javascript
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](https://github.com/sansk/project-euler-solutions-javascript/tree/main/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.**](https://theintrovertcoder.hashnode.dev/series/project-euler)

Thank you!