Project Euler Problem 5

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

There are two ways to solve this. You can either brute force the numbers or find the LCM of the numbers 1 to 20. In this case, brute forcing would not be a smart method since the final answer is 232792560 and WILL take a long time in PHP.

Brute Force PHP Script

<?php
$run = true;
$count = 0;
while($run) {
	$count++;
	$cur = 0;
	$i = 1;
	while($i < 21) {
		if($count % $i == 0) $cur++;
		else $i = 21;
		$i++;
	}
	if($cur == 20) {
		$run = false;
	}
}
echo $count;
?>

Finding the LCM

2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
11 = 11
12 = 2 * 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 * 2 * 2 * 2
17 = 17
18 = 3 * 3 * 3
19 = 19
20 = 2 * 2 * 5
LCM = 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560

Leave a Reply

Your email address will not be published.