Project Euler Q7 - 10001st prime

Question

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, when I tried timing it by passing it a million numbers to check, it didn't make any noticeable difference. When I tried to use it in my function to answer the original question, it churned away for a long time before I stopped the execution.

Anyone able to explain this? I'm still bothered that the fairly simple C# I saw did the whole thing much faster, without any caching, etc. I'm sure F# could do the same.

EDIT The 2nd The C# code mentioned seems to have disappeared from the PE forum, but here is a very slightly modified version of it, with timing added. You can just copy this as-is into LinqPad...

void Main() {
  Stopwatch sw = new Stopwatch();
  sw.Start();
  int currentPrimePosition = 1;
  long currentPrimeCandidate = 1;
  while (currentPrimePosition < 10001) {
    currentPrimeCandidate++;
    if (IsPrime(currentPrimeCandidate)) {
      currentPrimePosition++;
    }
  }
  sw.Stop();
  Console.WriteLine($"The answer is: {currentPrimeCandidate}, in {sw.ElapsedMilliseconds}ms");
}

public static bool IsPrime(long number) {
  if (number < 2) return false;
  if (number % 2 == 0) return false;
  long boundary = (long)System.Math.Floor(System.Math.Sqrt(number));
  for (long i = 3; i <= boundary; i += 2) {
    if (number % i == 0) return false;
  }
  return true;
}

This runs in about 20ms in my machine, which is still about 10 times faster than the best F# I have (using Veedrac's suggestions lower down).

Answer 1

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.