Project Euler Solution: Problem #5

According to the Project Euler website, “Project Euler is a series of challenging mathematical/computer programming problems…”

Always a fan of puzzles, I have decided to share my attempts and solutions here.

Note: If you are trying to solve Problem #5 for yourself, DO NOT READ AHEAD!

Problem #5

Problem Description

This problem asks for the smallest number that is evenly divisible by all of the numbers from 1 to 20.

Solution

As with <a href="”>Problem #1, this problem required the use of the modulo mathematical operator (%).

Essentially this solution is a loop that starts at 2520 (the smallest number divisible by 1-10) and increments by 2520. This is because no numbers that *aren’t* divisible by 2520 will not also be divisible by 1-10, so they certainly won’t be divisible by 1-20.

We check the modulo for 11-20 against the current number, and if any of them return a remainder, continue the loop. When we find a number divisible by 11-20, we know it is also divisible by 1-10, because it is divisible by 2520.

Code (PHP)

$exitLoop = false;
$x = 2520;
while (!$exitLoop) {
if ($x % 20 || // 20 gives us 1, 2, 4, 5, 10 as well
$x % 19 || // 19 is prime
$x % 18 || // 18 gives us 3, 6, 9 as well
$x % 17 || // 17 is prime
$x % 16 || // 16 gives us 2, 4, 8 as well
$x % 15 || // 15 gives us 3, 5 as well
$x % 14 || // 14 gives us 2, 7 as well
$x % 13 || $x % 12 || $x % 11) {
$x += 2520;
} else {
$exitLoop = true;
}
}

echo $x;

Final Number: 232,792,560

Chimeric Dream