## Problem 5: Smallest multiple

*Difficulty: Easy

Problem

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?

How to solve it:

As you may know, if the number is divisible by all the numbers from 1 to 20, it must first divisible by 20. With this in mind, we can come up with a pretty fast and simple solution.
Start from 20, check if the number’s divisibility , if it is, we stop and print out the result, if it not, we step forward 20 steps (as explained). This will dramatically decrease run time from hundreds of milliseconds to just a few dozens of milliseconds as we just step 1 step forward.

Implementation (Java):

public class Prob5 {

public static void main(String[] args) {

long cur = System.currentTimeMillis();

long n = 20;

while(!checkDivisibility(n)) {

n+=20;

}

System.out.println(n);

System.out.println(“Took “ + (System.currentTimeMillis() cur) +” ms”);

}

private static boolean checkDivisibility(long n) {

for(int i = 1; i <= 20; ++i)

if(n % i != 0) return false;

return true;

}

}