# Quicklyish finding primes by trial division

I ask because it seems to be taking waaaay more space/time than it should. Also, I know that if I want to be super efficient I should use Java's BitSet and a Sieve of Eratosthenes, but I wrote it like this to compare to a friend's implementation in C#.

(defn primes-upto [n]
(let [primes (transient [2 3])]
(loop [i 5]
(if (> i n)
(persistent! primes)
(do (when
(loop [j 0 is-prime true]
(let [p (primes j)]
(when is-prime
(if (> (* p p) i)
true
(recur (inc j) (not= 0 (mod i p)))))))
(conj! primes i))
(recur (+ i 2)))))))


I get (primes-upto 100000) taking about 40 ms. I can't make it go much faster, but I can make it reliable. At present, it isn't.

The program works:

(primes-upto 10) ;[2 3 5 7]


But if you take away the transients, it fails:

(defn primes-upto [n]
(let [primes [2 3]]
(loop [i 5]
(if (> i n)
primes
(do (when
(loop [j 0, is-prime true]
(let [p (primes j)]
(when is-prime
(or (> (* p p) i)
(recur (inc j) (not= 0 (mod i p)))))))
(conj primes i))
(recur (+ i 2)))))))

(primes-upto 10); java.lang.IndexOutOfBoundsException: null ...


The program is depending upon accidents of how transients are implemented. Transients don't promise to update their bindings. They revoke the promise of immutability.

Rewriting the program idiomatically, I get ...

(defn primes-upto [n]
(loop [primes [2 3], i 5]
(if (> i n)
primes
(let [i-prime? (loop [j 1]
(let [p (long (primes j))]
(or (> (* p p) i)
(and (not= 0 (mod i p))
(recur (inc j))))))]
(recur (if i-prime? (conj primes i) primes) (+ i 2))))))


... including a few variations:

• The inner loop is simpler, and employs and and or for brevity.
• Since we increment i by 2, we don't need to check for division by 2, so start with j at 1.
• Convert p to a long explicitly, to help with type inference.
• Dispense with transients.

When all's said and done, it's a little faster, but not much. Transients don't help much either.