# Solving the Project Euler Problems – Problem 5

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?

This one isn’t so much a problem of programming as it is mathematics, as it isn’t just a case of multiplying all the numbers from 1 to 20, that would just result in 20!, which is far bigger than our actual answer.

For reference 20! = 2,432,902,008,176,640,000, which is 2 quintillion 432 quadrillion 902 trillion 8 billion 176 million 640 thousand.

Taking into account the prime numbers up to 20 we have 2, 3, 5, 7, 11, 13, 17 and 19, so our number still needs to be divisible by 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 and 20. Our number so far is 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

By virtue of being multiples of these prime factors, our number is already divisible by 6 (2 × 3), 10 (2 × 5) and 14 (2 × 7). The numbers now remaining are 4, 8, 9, 12, 16, 18 and 20.

If we multiply our number by 2, it is now divisible by 4 (it was divisible by 2), 12 (it was divisible by 6) and 20 (it was divisible by 10). The numbers now remaining are 8, 9, 16 and 18 and our number is 2 × 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

Multiplying by 2 again will make our number divisible by 8, and doing it again will make it divisible by 16, leaving only 9 and 18 and making our number 2 × 2 × 2 × 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

Now multiplying our number by 3, as it was already divisible by both 3 and 6, will now make it divisible by 9 and 18.

Our number is now 2 × 2 × 2 × 2 × 3 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 116,396,280. Far smaller than our result for 20! above!

Incidentally, by virtue of being divisible by 3 and 7, our number is also divisible by 21. And as it’s divisible by 2 and 11, it is also divisible by 22.