Problem 007: 10001st prime

From Project Euler:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

My initial approach to this was to use a Sieve of Eratosthenes to efficiently find all the prime numbers up to a given limit, however that ended up spending a lot of processing in manipulating lists. Turns out there are faster ways to do it.

I also discovered that Clojure does not have tail-call recursion, you need to use the loop and recur constructs to avoid getting stack overflows.

There are two optimizations here. The first is that we'll skip the first prime 2, since it's obviously not the 10001st prime and it is an anomaly that doesn't let us use the next optimization, which is that all primes greater than 3 have the form $6k \pm 1$. Instead of iterating through each number or even each odd number, we'll iterate through all numbers of that form.

Here's the code:

(defn nth-prime [n]
  (loop [i (- n 2)
         k 1
         s -1]
    (let [p (+ (* 6 k) s)
          next-s (if (= s 1) -1 1)
          next-k (if (= s 1) (+ k 1) k)]
      (cond
        (not (is-prime? p)) (recur i next-k next-s)
        (= i 0) p
        :else (recur (- i 1) next-k next-s)))))

Running this code is actually surprisingly slow:

rob@alien ~/code/euler $ time clj 7.clj 
104743

real 0m16.076s
user 0m17.930s
sys 0m0.349s

I'll have to do some profiling to figure out why this is the case. When translating the code as-is to Python it takes 0.176s, and Python isn't exactly known for speed.