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; } }