Project Euler – Problem 5

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.

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

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 smallest number which is exactly divisible by a set of numbers, is the LCM (Least Common Multiple) of those numbers.

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

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

Finding the LCM of two numbers:

  1. A and B are the two integers whose LCM must be found.
  2. Initialize LCM as 1.
  3. 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.
  4. After no more divisions are possible, multiply LCM by A and B.
  5. This is the LCM of A and B.

Another approach to LCM:

HCF(a,b) * LCM(a,b) = a * b

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

Solution in C++

Advertisements
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: