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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.