## Question

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 10001st prime number?

## Clojure

#!/usr/bin/env clojure
(defn primes [n]
(defn improve [p nums]
(filter #(or
(not (= (rem % p) 0))
(= % p))
nums))
(defn prime-iter [p nums i]
(if (> (* p p) n)
nums
(prime-iter (nth nums (+ i 1)) (improve (nth nums (+ i 1)) nums) (+ i 1))))
(prime-iter 2 (range 2 (+ n 1)) -1))

(println (nth (primes 1000000) 10000))
$time ./10001st-prime real 0m0.008s user 0m0.004s sys 0m0.000s ## Haskell primes :: [Integer] primes = 2 : sieve primes [3,5..] where sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0] where (h, t) = span (< p*p) xs main :: IO () main = print$ primes !! 10000
$ghc -O2 -o 10001st-prime 10001st-prime.hs$ time ./10001st-prime
real   0m0.027s
user   0m0.024s
sys    0m0.000s

## JavaScript

const sieve = {}
let n = 0
for (var q = 2; n < 10001; q++) {
if (sieve[q]) {
sieve[q].forEach((p) => {
const list = sieve[p + q] || []
list.push(p)
sieve[p + q] = list
})
} else {
sieve[q * q] = [q]
n++
}
}
console.log(q - 1)
$time node --use-strict --harmony-destructuring 10001st-prime.js real 0m0.287s user 0m0.252s sys 0m0.032s ## Python #!/usr/bin/env python def eratosthenes(): '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.''' D = {} # map composite integers to primes witnessing their compositeness q = 2 # first integer to test for primality while 1: if q not in D: yield q # not marked composite, must be prime D[q*q] = [q] # first multiple of q not already marked else: for p in D[q]: # move each witness to its next multiple D.setdefault(p+q,[]).append(p) del D[q] # no longer need D[q], free memory q += 1 def nth_prime(n): for i, prime in enumerate(eratosthenes()): if i == n - 1: return prime print(nth_prime(10001)) $ time python3 find-primes.py
real   0m0.126s
user   0m0.100s
sys    0m0.016s

## Ruby

#!/usr/bin/env ruby
require 'mathn'
puts Prime.take(10001).last
\$ time ruby find-primes.rb
real   0m0.054s
user   0m0.048s
sys    0m0.004s