Project Euler Problem 5 – Scheme Style

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:

;; find the smallest number where n is 
;; divisible by all numbers in given list 
(define smallest-divisible-by 
(lambda (num-list) 
(let loop ((i 1)) 
(if (divisible-by i num-list) 
i 
(loop (+ i 1)))))) 

(define divisible-by 
(lambda (n lst) 
(if (null? lst) 
#t 
(if (= (remainder n (car lst)) 0) 
(divisible-by n (cdr lst)) 
#f)))) 

;; generates a list of numbers between start and end 
;; contract: number, number -> list 
(define make-list-range 
(lambda (start end) 
(if (> start end) 
'() 
(cons start (make-list-range (+ start 1) end))))) 

(smallest-divisible-by (reverse (make-list-range 1 20)))

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:

(lcm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

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.