Smallest Multiple

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?

Let’s make it easier

First, let’s try to decrease a bit the number of numbers we’ll need to check. We can analyze the simpler problem for which we already know the answer.

The 2520 is divisible by all numbers from 1 to 10. We know that among those numbers, 2, 3, 5, 7 are primes. So, if the number we’re looking for is divisible by all these prime numbers, then it must be a multiple of (2 × 3 × 5 × 7) = 210.

Solution

We can follow the same logic to find a number that’s evenly divisible by all numbers from 1 to 20.

Prime numbers in this set are: 2, 3, 5, 7, 11, 13, 17, 19. The number we’re looking for, then, must be a multiple of 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 9699690.

Let’s try to find that number!

object Euler005 extends EulerApp {
  // 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9699690
  override def execute(): Int = Iterator
    .from(9699690, 9699690)
    .find { n =>
      (2 to 20).forall(k => n % k == 0)
    }
    .get
}

If we wanted to improve it even further, then we can notice that we don’t need to check again if our numbers are divisible by all these prime numbers. Also, multiplies of these numbers, such as 6 (2 * 3), no need to be checked either.

That’s because every number that’s divisible by both 2 and 3 must be divisible by 6.

We don’t need to make it more complex than necessary. The current solution already runs in 1-2 ms on my machine.