Pete On Software

RSS Feed

Project Euler Problem 5 – Scheme Style

Least Common Multiple (from http://uva.onlinejudge.org/external/107/p10791.jpg)
Project Euler Problem 5 reads “What is the smallest number divisible by each of the numbers 1 to 20?” This is obviously a Least Common Multiple problem. There are 2 quick ways that come to mind to solve the problem. The first is that you can brute force it, checking all of the numbers until you find one that can be divided by all of the numbers.

After I arrived at my answer (by doing just that last year), I went into the Project Euler forums and found that quite a few people did it just the same way. Others actually attempted the prime factorization necessary to compute the least common multiple and had varying degrees of success.

With my recent foray into Scheme, I decided to hit the forums to see if anyone attempted problem 5 in Scheme. The first Scheme solution that I found was the following:

This was just a brute force method in Scheme. He created a list and then tried to find a number that was divisible by all of the numbers in the list. The bad news is that it took 97 seconds on my MacBook Pro with a Quad Core i5. That is completely unacceptable.

I got to thinking about it and I wondered if Scheme had a least common multiple function, as functional languages often have “neat math stuff” in their bag of tricks.

It turns out that it does. If I run this code:

It returns the answer as soon as I hit enter, computed almost instantly. It may be cheating to use a built-in function, but in real life, I don’t think so. I think you use the best tool for the job and if I can answer a problem with no development and an instant result, I think that that is the tool I should use.

One Comment

Pete  on September 14th, 2012

Removing comments on this post because spammers are trying to hit it at the rate of more than 1000 a day. Since there are no other comments on here, I’m probably safe in removing the feature 😉