Edit (18/01/2013)
I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.
Firstly
This is a solution to problem 5 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.
The original problem reads like this:
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 Algorithm
Firstly, there are two ways to solve this problem. One involves brute force, and one requires a little savvy.
Technically, there are a whole bunch of ways to solve this problem – dependant on your understanding of Mathematics. Hopefully, both of these methods will be simple enough to follow – assuming you can understand Prime Numbers.
The brute force check goes like this:
- Start at n, check this against all numbers in m
- If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
- If not, add 1 to n and start again.
“n” starts at 1 (this is the smallest positive number that will divide by all the numbers from 1 to 20)
“m” starts at 1 and goes only as far as 20 (this is the series of numbers that “n” has to divide by)
That’s it.
The smarter algorithm goes like this:
- Start with n at 2520
- If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
- If not, add 2520 to n and start again.
This method assumes that you recognise a few things from the problem statement. Let’s take another look:
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?
Since the numbers between 1 and 20 contain all the numbers between 1 and 10 (1, 2, 3, 4, 5, 6, 7, 8, 9 & 10), some of the work is done for us. We can assume that, since 2520 is evenly divisible by all numbers between 1 and 10, that it must be evenly divisible by all the numbers between 1 and 20.
This algorithm speeds up execution exponentially. Instead of going through every positive integer between 1 and he final answer, we can jump in steps of 2520.
The Code
I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.
So, without further ado, here is the finished code:
And there you have it, another problem solved (and optimised) in minutes.
Until next time,
J
