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?

#### Solution - PHP

My first solution was of course to brute force it with while and for loop checking if the numbers if they are divisible from 1 to 20 which took a lot of time to finish, i take its not going to the best solution.

function divby($number,$divisor) { for ($i=2; $i <= $divisor; $i++) if (!($number%$i == 0)) return false; return true; } $number=20; $divisor=20; while (!divby($number,$divisor)) $number += 20; echo $number;

Manual approach will be easier when we are solving for few numbers like finding the smallest multiple of the numbers 7,8,9. We can just multiply them 4*5*6 = 120, but there would be a question: is this the smallest multiple? And it is not, its 60. How do we get 60?

The answer is by using LCM or the least common multiple. For example if we want to get the LCM(4,5,6) that would be 2^2 * 5^1 * 3^1 = 60

That is getting the multiples of 4, 5 and 6 and multiplying their product.

4 can be expressed as 2^2

5 can be expressed as 5^1

and 6 can be expressed as 2^1 * 3*1

To get the LCM we will only need the factors with the highest integer, that is 2^2*5*1*3^1. Hence, 4*5*3 = 60

Therefore, if we get the LCM of the numbers (1 .. 20) we will get the solution for our problem.

First we need to decompose the numbers 1-20 into prime powers then we get the products of those factors with highest exponents and all the prime numbers. The solution is better illustrated by the table below:

2 => 2^1 3 => 3^1 4 => 2^2 5 => 5^1 6 => 2^1 3^1 7 => 7^1 8 => 2^3 9 => 3^2 10=> 2^1 5^1 11=> 11^1 12=> 2^2 3^1 13=> 13^1 14=> 2^1 7^1 15=> 3^1 5^1 16=> 2^4 17=> 17^1 18=> 2^1 3^2 19=> 19^1 20=> 2^2 5^1 ============================================================= 2^4 3^2 5^1 7^1 11^1 13^1 17^1 19^1

From the table above we get the prime factors as 2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17*1 * 19*1

Now, converting it to PHP code we get:

<?php // http://en.wikipedia.org/wiki/Greatest_common_divisor // gcd(a,0) = a // gcd(a,b) = gcd(b,a%b) function gcd($a,$b){ return ($b == 0) ? $a : gcd($b,$a%$b); } // http://en.wikipedia.org/wiki/Least_common_multiple // lcm(a,b) = floor(a*b)/gcd(a,b) function lcm($a, $b) { return ( $a / gcd($a,$b) ) * $b; } $divisor = 1; $limit = 20; for ($i=2; $i<=$limit;$i++) $divisor = lcm($divisor, $i); echo $divisor;