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;

              }

}

Advertisements