The Problem

Find the 10001st prime number.

F# Solution

We already wrote some functions to generate sequences of prime numbers for Problem 3. We’re going to be using those functions over and over again so I’ll probably just wind up moving them to a module. But today is not that day.

That code generated a sequence of primes below a certain number. I’m going to modify that code to generate a sequence of n primes.

let intsqrt i = int(sqrt(float i))

let isPrime i =
    if i <= 1 then false
    elif i = 2 then true
    elif (i &&& 1) = 0 then false
    else
        let sr = intsqrt i
        seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime x =
    match x with
    | x when isPrime x -> x
    | x -> nextPrime (x + 1)

let getSomePrimes num =
    let primeGenerator (candidate,count) =
        if count > num then
            None
        elif candidate = 2 then
            Some(2,(3,count+1))
        else
            let next = nextPrime candidate
            Some(next,(next+2,count+1))

    Seq.unfold primeGenerator (2,1)

getSomePrimes uses Seq.unfold with a generator function that generates the next prime after the current one. It stops when num elements have been generated.

With this code in place, we can simply generate a sequence containing 10001 primes and use Seq.last to give us the answer:

getSomePrimes 10001
|> Seq.last