Problem 5, from the Project Euler website:

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?

This problem can easily be solved by using brute force, in about 3.61 seconds. While that’s not ** blazing**, it’s under the one – minute time limit.

A more logical approach gives the answer in **0.02 seconds**. I will take up both methods and discuss them.

## General Algorithm I

This is the brute force method. It involves continuous iteration untill a number is found which is divisible by all the numbers from 1 to 20.

- Declare
*i*= 1; - Repeat the following steps:
- Divide
*i*by all the numbers from 1 to 20. - If it is not perfectly divisible by any of the numbers, increment
*i*and continue. - If it is perfectly divisible then
*i*is the number we are looking for. Print*i*and break the loop.

- Divide

This method gives a run-time of about **8 seconds**. One slight modification can be made:

Instead of dividing from 1 to 20, it is sufficient to check from **11 to 20, **because all the number within this range are multiples of the preceding numbers.

Making the above modifications cuts down the run-time to the mentioned **3.61 seconds. **

## General Algorithm II

A little elementary maths go into this approach:

The

which is exactly divisible bysmallest numbera set of numbers, is the LCM (LeastCommonMultiple) of those numbers.

So the number that we’re looking for is the LCM of the numbers 1 through 20.

*int Answer*= 1.- Iterate
*i*from 1 to 20. *Answer*is now the LCM of*i*and*Answer*.- At the end of the loop, the value of
*Answer*is the required number.

Finding the LCM of two numbers:

and*A*are the two integers whose LCM must be found.*B*- Initialize
as 1.*LCM* - If
**both***A*and*B*are divisible by any integer from 2 to*A*, divide**both***A*and*B*by that integer and multiply the LCM by it. Also, begin checking for common factors from 2. - After no more divisions are possible, multiply
by*LCM**A*and*B.* - This is the
*LCM*of*A*and*B.*

Another approach to LCM:

Figure out an algorithm for the HCF of two numbers by yourself! 🙂