# Naïve Prime Factorization in Clojure

I saw a question about prime factorization on Stack Overflow and realized I had never attempted it before. This was what I ended up with after some playing around and tweaking.

I'd like improvements on anything here.

• I know I could use a sieve instead of the naive method (I may switch later), but it was sufficient here. Is there a better way though to handle 2 in prime?? I feel like it being a special case is off.

• Is there a better way than a full loop for the main function?

• Whatever else

(find-prime-factors 993061001)
=> [17 173 337661]


Verified against CalculatorSoup.

(ns irrelevant.prime-factorization)

(defn is-factor-of? [n multiple]
(zero? (rem n multiple)))

(defn prime? [n]
(or (= n 2) ; TODO: Eww
(->> (range 2 (inc (Math/sqrt ^double n)))
(some #(is-factor-of? n %))
(not))))

(defn primes []
(->> (range)
(drop 2) ; Lower bound of 2 for the range
(filter prime?)))

(defn smallest-factor-of? [n possible-multiples]
(some #(when (is-factor-of? n %) %)
possible-multiples))

(defn find-prime-factors [n]
(loop [remaining n
remaining-primes (primes)
prime-factors []]

(if-let [small-prime (and (> remaining 1) (smallest-factor-of? remaining remaining-primes))]
(let [rest-primes (drop-while #(not= % small-prime) remaining-primes)]
(recur (long (/ remaining small-prime))
rest-primes
(conj prime-factors small-prime)))

prime-factors)))