#### Problem 5: Smallest Multiple

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?

#### The Catch

How to efficiently check whether an arbitrary number **x **is divisible by all of the numbers from 1 to 20; dividing **x** by all numbers from 1 to 20 is called brute forcing and is not efficient.

#### The Light

Manipulate the divisibility rules to lessen check points: If **x** is divisible by 20, then **x** is also divisible by 2, 4, 5, 10 (because they are factors of 20). If **x** is divisible by 18, then **x** is also divisible by 2, 3, 6, 9 (because they are factors of 18).

That leaves 7, 8, 11, 12, 13, 14, 15, 16, 17, 19 unchecked, but checking divisibility by 14 will take care of 7 and checking divisibility by 16 will take care of 8. As a result, the only necessary check points are **11, 12, 13, 14, 15, 16, 17, 18, 19, 20**; immediately return if divisibility test fails for any of these check points.

#### The Code

public class Problem5 { public static void main(String[] args) { int n = 20; while(!isDivisible(n)) { n += 20; //Increment by 20 to speed up because n has to be divisible by 20 } System.out.println(n); } public static boolean isDivisible(int n) { if( n % 20 != 0 || n % 18 != 0 || n % 19 != 0) return false; for(int i = 11; i < 18; i++) { if(n % i != 0) return false; } return true; } }