Project Euler

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