# Project Euler Problem 5

Here’s the link to the problem description. My first try at the problem resulted in a slow but working implementation.

(defn multiple-of-all? [n factors]
(every? #(zero? (rem n %)) factors))

(defn least-common-multiple [nums]
(let [ns (sort > nums)
mx (first ns)]
(first (filter #(multiple-of-all? % ns) (iterate #(+ mx %) mx)))))

(least-common-multiple (range 2 21))

A peek at what other people wrote revealed that once again, I went with a stupid search-based idea instead of looking at the mathematical structure of the problem.

An elegant three-line solution submitted anonymously was my favorite, and is very fast:

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))
(reduce #(lcm %1 %2) (range 1 21))

1. Using recur in gcd leads to a simple, efficient definition.
3. Using reduce is the right idiom for “multiplication-like” algorithms such as this.
Once again, it seems it is useful to check if a problem easily fits into the reduce abstraction.