Number factorization in clojure

Question

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))
 (factorize (/ num head) (cons head acc) primes)
 (recur rest))))))

Answer 1

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 [1], 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.

Answer 2

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.