Problem #5 is ranked as one of the easiest problems on the site:
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 number that is evenly divisible by all of the numbers from 1 to 20?
Its an easy problem in any programming language.
start at 1 and keep incrementing. Every step of the way check the number modulo 2-20, if they all come out to 0, you've got the answer.
Thats the fastest program to write, however it'll take more than 4.6 billion steps before you reach it.
There are several optimizations one could do to speed things up as demonstrated in this blog post:
http://www.fsharp.it/2008/02/07/project-euler-in-f-problem-5/
showing how to find the solution in around 25 seconds using F#.
After looking at the code I was impressed with F# and the author's optimization abilities and techniques. But it does show a glaring problem in post optimizations and fundamental shift in computer science away from field of number theory and mathematics which it came from.
25 seconds isn't too bad for something that could take 4.6 billion steps, but using some simple number theory and prime factorization I can give you the answer in about as much time. Here's the solution for 1-10 as I don't want to give the final answer away.
Before we start here's something to think about, if a number is divisible by 8, then it is divisible by 4 and 2 so why do the redundant checking.
here are our numbers omitting 1:
2, 3, 4, 5, 6, 7, 8, 9, 10
and the prime factorizations:
2
3
2, 2
5
2, 3
7
2, 2, 2
3, 3
2, 5
back the being divisible by 8, thats: 2, 2, 2
so lets go through and knock out any number of 2s less than 3 for a given factorization
3
5
7
2, 2, 2
3, 3
and we repeat that with nine's: 3, 3
5
7
2, 2, 2
3, 3
and lastly with five:
7
2, 2, 2
3, 3
which leaves you with 7, 2, 2, 2, 3, 3, 5
7*2*2*2*3*3*5 = 2520
A similar method would be to start with 2 and 3. find the lcm(2, 3) = 6.
then find the lcm(6, 4) = 12
lcm(12, 5) = 60
lcm(60, 6) = 60
lcm(60, 7) = 420
lcm(420, 8) = 840
lcm(840, 9) = 2520
lcm(2520, 10) = 2520
4 comments:
Since lcm (x,y) is easily calculated as x*y / gcd (x,y), and the gcd function is easy to implement efficiently, it seems like the second method is the easiest to efficiently program. I'm reasonably sure such a program would arrive at the answer in much less than 25 seconds, even in an interpreted language. :-)
As a math guy, I probably wouldn't even use a computer on this one, either; I'd just do it your first way.
Indeed, I went with the accumulated LCM function in python and it ran too quick to take a wall clock time.
Post a Comment