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 clojure find-primes.clj
real   0m1.139s
user   0m2.226s
sys    0m0.108s

Go

package main

import "fmt"

func iSqrt(n int64) int64 {
    var r1, r int64 = n, n + 1
    for r1 < r {
        r, r1 = r1, (r1+n/r1)>>1
    }
    return r
}

func PrimeSieve(n int64) []int64 {
    result := make([]int64, 0, n)
    sieve := make([]bool, n+1)
    sn := iSqrt(n)
    var i, j int64
    for i = 2; i <= sn; i++ {
        if !sieve[i] {
            for j = i * i; j <= n; j += i {
                sieve[j] = true
            }
        }
    }
    for i = 2; i <= n; i++ {
        if !sieve[i] {
            result = append(result, i)
        }
    }
    return result
}

func main() {
    primes := PrimeSieve(1000000)
    fmt.Println(primes[10000])
}

$ go build -o 10001st-prime 10001st-prime.go
$ time ./10001st-prime
real   0m0.005s
user   0m0.000s
sys    0m0.006s

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.025s
user   0m0.016s
sys    0m0.008s

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 10001st-prime.js
real   0m0.133s
user   0m0.148s
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.112s
user   0m0.104s
sys    0m0.008s

Ruby

#!/usr/bin/env ruby
require 'mathn'
puts Prime.take(10001).last

$ time ruby find-primes.rb
real   0m0.058s
user   0m0.050s
sys    0m0.007s

Rust

fn eratosthenes(limit: usize) -> Vec<usize> {
    let mut sieve = vec![true; limit];
    let mut p = 2;
    loop {
        // Eliminate multiples of p.
        let mut i = 2 * p - 1;
        while i < limit {
            sieve[i] = false;
            i += p;
        }
        // Find the next prime.
        if let Some(n) = (p..limit).find(|&n| sieve[n]) {
            p = n + 1;
        } else {
            break;
        }
    }
    sieve
        .iter()
        .enumerate()
        .filter(|&(_, &is_prime)| is_prime)
        .skip(1)
        .map(|(i, _)| i + 1)
        .collect()
}

fn main() {
    let primes = eratosthenes(1000000);
    println!("{}", primes[10000]);
}

$ rustc -C target-cpu=native -C opt-level=3 -o sieve sieve.rs
$ time ./sieve
real   0m0.007s
user   0m0.007s
sys    0m0.000s