# Project Euler Problem 7 Solution

## 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.005s 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.029s
user   0m0.028s
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 10001st-prime.js real 0m0.233s user 0m0.220s sys 0m0.012s ## 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.090s
user   0m0.088s
sys    0m0.000s

## Ruby

#!/usr/bin/env ruby
require 'mathn'
puts Prime.take(10001).last
$time ruby find-primes.rb real 0m0.100s user 0m0.092s sys 0m0.004s ## 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.015s
user   0m0.012s
sys    0m0.000s