Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created August 22, 2022 01:59
Show Gist options
  • Save ericnormand/5c744622c99a1486c90ada14ce9e6c85 to your computer and use it in GitHub Desktop.
Save ericnormand/5c744622c99a1486c90ada14ce9e6c85 to your computer and use it in GitHub Desktop.
475 Eric Normand Newsletter

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

@souenzzo
Copy link

Trying to follow the definition of lcm

(defn lcm
  [vs]
  (some
    (fn [n]
      (when (every?
              #(zero? (mod n %))
              vs)
        n))
    (range 2 (inc (apply * vs)))))

@Toni-zgz
Copy link

Toni-zgz commented Aug 22, 2022

(ns lcm)
(require '[clojure.test :as test])

(defn lcm [vect]
    (if (= vect [])
        nil
        (let [mcd (fn [a b]
                    (loop [a1 a
                           b1 b]
                        (if (= b1 0)
                            a1
                            (recur b1 (mod a1 b1)))))
              mcm (fn [a b] (/ (* a b) (mcd a b)))]
          (reduce mcm vect))))

(test/deftest lcm-test
  (test/is (= nil (lcm [])))
  (test/is (= 10  (lcm [10])))
  (test/is (= 4   (lcm [2 4])))
  (test/is (= 21  (lcm [3 7])))
  (test/is (= 20  (lcm [2 4 10])))
  (test/is (= 60  (lcm [15 2 4]))))

(test/run-tests 'lcm)

@nbardiuk
Copy link

(defn gcd [a b]
  (cond
    (= 0 b) a
    (< a b) (gcd b a)
    :else   (gcd b (mod a b))))

(defn lcm
  ([]    nil)
  ([a b] (/ (* a b) (gcd a b)))
  ([xs]  (reduce lcm xs)))

@gerritjvv
Copy link

gerritjvv commented Aug 22, 2022

;; Finding the least common multiplier for a list of numbers
;; Reference material
;; https://en.wikipedia.org/wiki/Least_common_multiple
;; https://en.wikipedia.org/wiki/Euclidean_algorithm
;; https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
;; https://octave.sourceforge.io/octave/function/lcm.html


(defn euclid-gcd [^long a ^long b]
      "Simple eclidean gcd https://en.wikipedia.org/wiki/Euclidean_algorithm"
      (loop [a' (long (max a b)) b' (long (min a b))]
            (if (zero? b')
              a'
              (recur b' (mod a' b')))))

(def ^:dynamic *gcd* euclid-gcd)

(defn lcm
      ([])
      ([^long a ^long b]
       (* a (/ b (*gcd* a b))))
      ([ls]
       (reduce lcm ls)))

@mchampine
Copy link

mchampine commented Aug 22, 2022

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

@miner
Copy link

miner commented Aug 22, 2022

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))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment