# Project Euler

### A Taste of Number Theory

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