1
\$\begingroup\$

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)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.