Quicklyish finding primes by trial division

Question

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)))))))

Answer 1

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.