Factorization of Eratosthenes
Adapts the Sieve of Eratosthenes to prime factorize numbers through n.
(defn prime-factors [n]
(reduce
(fn [factors prime]
(if (= 1 (count (nth factors prime)))
(reduce
(fn [factors multiple]
(let [[composite-divisor :as divisors] (nth factors multiple)]
(if (< prime composite-divisor)
(let [remaining-divisor (/ composite-divisor prime)
remaining-divisors (nth factors remaining-divisor)
prime-divisors (cons prime (rest divisors))]
(assoc
factors multiple
(if (< 1 (count remaining-divisors))
(concat remaining-divisors prime-divisors)
(cons remaining-divisor prime-divisors))))
factors)))
factors
(range (* prime prime) (inc n) prime))
factors))
(mapv list (range (inc n)))
(range 2 (inc (m/sqrt n)))))(prime-factors 13)[(0)
(1)
(2)
(3)
(2 2)
(5)
(3 2)
(7)
(2 2 2)
(3 3)
(5 2)
(11)
(3 2 2)
(13)]