# Number factorization in clojure

I'm just a Clojure noob (started learning yesterday). Here is my helloworld program. It factorizes number into primes. Do you have any comments? How could I make this code cleaner and shorter? Maybe I can deduplicate some things?

(defn lazy-primes
([] (cons 2 (lazy-seq (lazy-primes 3  [ 2 ]))))
([current calculated-primes]
(loop [ [first-prime & rest-primes] calculated-primes]
(if (> (* first-prime first-prime) current)
(cons current (lazy-seq (lazy-primes
(inc current)
(conj calculated-primes current))))
(if (= 0 (mod current first-prime))
(lazy-seq (lazy-primes (inc current) calculated-primes))
(recur rest-primes))))))

(defn factorize
([num] (factorize num '(1) (lazy-primes)))
([num acc primes]
(if (= num 1) acc
(loop [ [head & rest] primes ]
(if (= 0 (mod num head))
(recur rest))))))


Wow! If this is you after one day, we hope for great things.

However, you can make your program simpler. Let's start with factorize. It has a couple of defects:

• It uses proper recursion where tail recursion with recur would suffice. So it would overflow the stack for a number having too many factors. However, since it uses long arithmetic, no number is big enough to do this.
• Each recursive call retries all the primes that have failed to be factors.

You can do it with a single loop if you exhaust each prime factor as you go:

(defn factorize [num]
(loop [num num, acc , primes (lazy-primes)]
(if (= num 1)
acc
(let [factor (first primes)]
(if (= 0 (mod num factor))
(recur (quot num factor) (conj acc factor) primes)
(recur num acc (rest primes)))))))


Now let's look at lazy-primes. While sticking to your algorithm ...

• We can simplify the base case - the one with no arguments.
• You produce a lazy sequence level for every number tested. We can use recur to short-circuit tail recursion for all the numbers that fail to be prime.
• We can use take-while, map, and not-any? to express the prime testing more clearly (though it will run slower). Because these are lazy, we don't do any redundant testing.

The result is

(defn lazy-primes
([] (lazy-primes 2 []))
([current known-primes]
(let [factors (take-while #(<= (* % %) current) known-primes)
remainders (map #(mod current %) factors)]
(if (not-any? zero? remainders)
(lazy-seq (cons
current
(lazy-primes (inc current) (conj known-primes current))))
(recur (inc current) known-primes)))))


A couple of arbitrary changes:

• I've used the abbreviated #(...) function syntax.
• I renamed calculated-primes to known-primes.

Edited to correct an erroneous comment.

Based on @Thumbnail answer there is still one little improvement, which leads to about twice increasing of performance: There is no prime numbers which is even we can just increment next value by two instead of one. So:

(defn lazy-primes
([] (cons 2 (lazy-primes 3 [])))
([current known-primes]
(let [factors (take-while #(<= (*' % %) current) known-primes)]
(if (not-any? #(zero? (mod current %)) factors)
(lazy-seq (cons current
(lazy-primes (+' current 2) (conj known-primes current))))
(recur (+' current 2) known-primes)))))


I also use *' operator instead of * because the prime numbers could be extremly large, so we need a large math here, but it's up to You.

Also, I removed on extra call, which also increase perfomance, not much - but worth it

So, little test results:

(time (last (take 10001 (old-lazy-primes))))


"Elapsed time: 37620.542326 msecs"

(time (last (take 10001 (lazy-primes))))


"Elapsed time: 18385.229566 msecs"

(time (last (take 10001 (lazy-primes)))) ;;without extra call


"Elapsed time: 11152.063344 msecs"

Yep, now it's faster triple as much.

UPDATE I removed the let expression gives a huge boost!

(defn lazy-primes
([] (cons 2 (lazy-primes 3 [])))
([current known-primes]
(if (not-any? #(zero? (mod current %))
(take-while #(<= (*' % %) current) known-primes))
(lazy-seq (cons current
(lazy-primes
(+' current 2)
(conj known-primes current))))
(recur (+' current 2) known-primes))))


So let's test:

(time (last (take 10001 (lazy-primes))))


"Elapsed time: 4535.442412 msecs"

It's because of how not-any works. If this function on some point find that predicate for some value is false - just returns true and assuming that take-while is lazy... here we go! On my modern computer this function takes ~300 msec to count 10001 prime number.