475 Eric Normand Newsletter

00 Least common multiple.md

Least common multiple

Write a function that finds the least common multiple of a collection of numbers. Remember that the least common multiple is the smallest integer that is evenly divisible by all the numbers in the collection.

Examples:

(lcm []) ;=> nil (undefined)
(lcm [10]) ;=> 10
(lcm [2 4]) ;=> 4
(lcm [3 7]) ;=> 21
(lcm [2 4 10]) ;=> 20
(lcm [15 2 4]) ;=> 60

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

(defn lcm [[f & r]]
  (loop [i f]
    (if (every? #(zero? (mod i %)) r) i
      (recur (+ i f)))))

I'm assuming all positive ints. Supporting zero or negatives would require more defensive code.

(defn lcm [nums]
  #_ {:pre [(every? pos-int? nums)]}
  (let [gcd (fn [x y]
              (if (zero? y)
                x
                (recur y (rem x y))))]
    (when (seq nums)
      (reduce (fn [x y] (quot (* x y) (gcd x y))) 1 nums))))