core.clj

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

(defn decompose [number]
  (let [factorpair (first (factor-pairs number))]
    (if (empty? factorpair) (list number)
        (concat (decompose (first factorpair))
                (decompose (second factorpair))))))

spec.clj

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [clojure.core.logic :refer [lvar]]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (ƒ [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (ƒ [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

(describe "Decomposition"
          (it "decomposes 1 into itself"
              (should= '(1) (decompose 1)))
          (it "decomposes primes into themselves"
              (should= '(2) (decompose 2))
              (should= '(3) (decompose 3))
              (should= '(17) (decompose 17))
              (should= '(23) (decompose 23)))
          (it "decomposes 2 * a prime into 2 and itself"
              (should= '(2 2) (decompose 4)))
          (it "decomposes a composite into its prime factorization"
              (should= '(2 2 2) (decompose 8))
              (should= '(2 3 5) (decompose 30))
              (should= '(2 11 11) (decompose 242))
              (should= '(2 5 11 23) (decompose (* 23 5 2 11)))))

(run-specs)