Project Euler Q7 - 10001st prime

The problem is (source)...

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?

This is my second attempt at the problem, and gets the correct answer in about a second. I wasn't too unhappy with that until I noticed a C# solution in the PE forum that ran in about 50ms.

Anyone able to suggest how I could improve my code, either in style or in speed?

let nthPrime n =
  let primeInner n =
    let numbers = [2..(int (sqrt (float n)))] // All ints from 2 to the square root of n
    (numbers |> Seq.filter (fun n1 -> n % n1 = 0) |> Seq.sum) = 0
  let rec nthPrimeInner target counter candidate last =
    if counter = target then last
    else if (primeInner candidate) then nthPrimeInner target (counter + 1) (candidate + 1) candidate
    else nthPrimeInner target counter (candidate + 1) last
  nthPrimeInner n 0 2 2

EDIT Following John Palmer's comment, I realised that I forgot to include my prime checking function. I've added it as an inner function in the code above.

Before I get on to caching (which is a good idea, but a second stage), I thought it might be worth trying a slightly different approach for the prime checking function. The code shown above iterates through all numbers from 2 to sqrt n, and then checks to see if the resultant sequence sums to zero. This means that for an even number, where the very first check (dividing by 2) is enough to say the number isn't prime will still result in 3..sqrt n being checked. So, I tried the following instead...

let primeInner n =
  let numbers = seq {for i in 2..(int (sqrt (float n))) -> i}
  numbers |> Seq.forall (fun n1 -> n % n1 = 0)

As far as I understand it, Seq.forall will give up as soon as it finds one element in the sequence for which the function doesn't return true. Thus, in the case of an even number, it would only need to check the very first input. This should have made the computation much faster. However,

This computation is wrong:

let primeInner n =
 let numbers = seq {for i in 2..(int (sqrt (float n))) -> i}
 numbers |> Seq.forall (fun n1 -> n % n1 = 0)

You need to invert the condition to n % n1 <> 0. Then you find a noticeable speed improvement of roughly 10x to the overall algorithm.

You should think of better names. isPrime instead of primeInner; findNth instead of nthPrimeInner.

A much prettier way is to filter an infinite sequence with isPrime and take the nth.

let nthPrime n =
  let isPrime n =
    seq {2..(int (sqrt (float n)))}
    |> Seq.forall (fun n1 -> n % n1 <> 0)

  let rec potentialPrimesFrom n =
    seq { yield n; yield! potentialPrimesFrom (n + 1) }

  potentialPrimesFrom 2
  |> Seq.filter isPrime
  |> Seq.nth n

This adds a little overhead, but you can get some of that back by applying nicer filters upfront to potentialPrimes

let potentialPrimes =
    let rec oddFrom n = seq { yield n; yield! oddFrom (n+2) }
    seq { yield 2; yield! oddFrom 3 }

  potentialPrimes
  |> Seq.filter isPrime
  |> Seq.nth n

Rather than pushing performance further here, I would suggest rewriting to a more optimal algorithm like a Sieve of Eratosthenes.

StackExchange Code Review Q#117889, answer score: 3