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
prime?? I feel like it being a special case is off.
Is there a better way than a full
loopfor the main function?
(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)))