After my last review request, I decided to try and make a "tree" visualization, and thought that I could benefit from making find-prime-factors lazily produce prime factors so the visualization can be updated in real time as factors are found.
This is what I ended up with. I was actually surprised how easy it was to adapt the loop to a recursive lazy-seq solution. The non-return accumulators were added as parameters to a recursive function, and the lazy return list was created via the typical (lazy-seq (cons ... ...)). It actually performs identically to the previous strict version too when evaluation is forced using vec.
If anyone sees anything here that can be commented on, I'd like to know.
(doseq [p (lazily-find-prime-factors 99930610001)]
(println p
(int (/ (System/currentTimeMillis) 1000))))
163 1544998649
191 1544998692
3209797 1544998692
Same as in the last review:
(ns irrelevant.prime-factorization.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))
Updated:
(defn lazily-find-prime-factors [n]
(letfn [(rec [remaining remaining-primes]
(when-let [small-prime (and (> remaining 1)
(smallest-factor-of? remaining remaining-primes))]
(lazy-seq
(cons small-prime
(rec (long (/ remaining small-prime))
(drop-while #(not= % small-prime) remaining-primes))))))]
(rec n (primes))))
1 Answer 1
All that the lazily-find-prime-factors function needs is the (primes) sequence. You just keep trying each in turn. Your smallest-factor-of drops the failed factors, but forgets what it has done, so you have to do it again for the recursive call.
And I'd rename your is-factor-of? function:
=> (is-factor-of? 4 2)
true
=> (is-factor-of? 2 4)
false
... reads wrongly. I've called it divides-by?.
I end up with ...
(defn lazily-find-prime-factors [n]
(letfn [(rec [remaining remaining-primes]
(when (> remaining 1)
(let [rp (drop-while #(not (divides-by? remaining %)) remaining-primes)
small-prime (first rp)]
(lazy-seq (cons small-prime
(rec (quot remaining small-prime) rp))))))]
(rec n (primes))))
Factoring the problem this way, you can easily plug in an efficient way of generating primes.