Project Euler - Problem 5 Solution With PHP

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 is the fastest and shortest way I could find. (I am only focused to the given numbers 1 to 20)

As far as I can calculate throughout mind, the number should be incremented by minimum 60 which is the smallest number that can be divided by 20 and 15.

20 * 3 = 4 * 15 = 60

Lets start with a loop which will increase the $number and start from 2520 just because we know that it works with the numbers 1 to 10.

This loop will run until we redefine the $okay variable. (When all remainders from the divisions we do is equal to zero.)

Just like I just said we loop through the divisors we defined at the begining. If the result meets our requirements we stop the loop by setting $okay to true.

PS: There are only 10 numbers becuase we want to keep it as simple and fast as possible. Since we know that if a number is evenly divisible to 20, its also evenly divisible to 10, 5 and 2 so we disgard them to faster the loop.

$okay = false;

$divisors = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11];

for ($number = 2520; !$okay; $number += 60) 
{
    foreach ($divisors as $divisor) 
    {
        if ($number % $divisor != 0) 
        {
            $okay = false;
            break;
        }
        $okay = true;
    }
}

echo $number;

Execution time: 1.5780s

Copyright © Ozan Kurt 2015.

Scroll to Top