Project Euler: Problem 5

Problem: Find the smallest number with all the integers 1 to 20 as factors (i.e. divisible without a remainder).

Q. What is the simplest way to find the lowest number with a given set of factors?
A. Try each number from 1 upwards, dividing it by every one of the factors.

Q. How do we reduce the search space?
A. Step over numbers based on the highest factor. In this case, we only need to check every 20th number (20, 40, 60 etc.), because any number between those will not be divisible by the highest factor. This reduces the search space by 95%.

Q. How do we reduce the number of divisions required, as this is a relatively expensive operation compared to other arithmetic operators?
A1. Only check the top half of factors, in this case 11-20. Every factor f in the bottom half is itself a factor of one of the factors in the top half (e.g. 6 is a factor of 12), and therefore does not need to be checked. This reduces the number of calculations by 50%.
A2. Do not check the highest factor (20), as we are using that to step through the candidate numbers, and therefore each candidate will already have 20 as a factor. This reduces the number of calculations by a further 10% (or 5% of the total).

<?php

declare(strict_types=1);
error_reporting(E_ALL);

$highest_factor = 20;
$lowest_factor = floor($highest_factor / 2) + 1;
$factors = range($lowest_factor, $highest_factor - 1);
$factors_count = count($factors);
$lowest_found = false;
$lowest_factorised = 0;

for ($candidate = $highest_factor; !$lowest_found; $candidate += $highest_factor)
{
    $lowest_found = true;

    for ($i = 0; $i < $factors_count && $lowest_found; $i++)
    {
        if ($candidate % $factors[$i] !== 0)
        {
            $lowest_found = false;
        }
    }

    if ($lowest_found)
    {
        $lowest_factorised = $candidate;
    }
}

print("$lowest_factorised\n");