3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ well you can cheat a little and start from 3 as the 2nd prime and then increase by 2 rather than 1. Also, speed depends on your prime function. In this case there is plenty of oppurtunity for caching \$\endgroup\$ – John Palmer Jan 26 '16 at 0:37
  • 2
    \$\begingroup\$ @JohnPalmer Please put all suggestions for improvements as answers rather than comments. \$\endgroup\$ – 200_success Jan 26 '16 at 1:00
  • \$\begingroup\$ @JohnPalmer Reading your comment, I realised that I forgot to include my prime function. I've edited my question to include it, and have also added a note about my first attempt to optimise it. Please can you take a look and see if you can explain why it failed? Thx \$\endgroup\$ – Avrohom Yisroel Jan 26 '16 at 14:13
  • \$\begingroup\$ @AvrohomYisroel I created a solution in C# for this euler's in around 50 ms. The key difference is that I use a bool[] to keep track if a number is prime or not instead of a int[] then I iterate over that bool[iterator] until I count 10001 primes. I use a technique called Sieve of Eratosthenes to create the list. here's a reference: csharphelper.com/blog/2014/08/… \$\endgroup\$ – wentimo Jan 26 '16 at 19:20
  • \$\begingroup\$ @wentimo Thx, but doing it fast in C# isn't the issue. I want to know why my F# code is so much slower, and how it can be improved. By the way, your sieve algorithm can be made much faster by observing that you only need to check numbers up to the square root of your max. Thanks for the reply. \$\endgroup\$ – Avrohom Yisroel Jan 26 '16 at 20:50
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great reply! I'm fairly new at F#, so still learning a lot. I tried inverting the condition, but didn't find it made very much difference at all. I can see why it should, as Seq.forall can bail out early as soon as it finds a divisor, but in practice it was only marginally quicker. However, the other approach was much faster. My first attempt used a sieve, but the problem with that algorithm is that you have to know the upper bound in advance. In the case here, who knows how big the nth prime would be, so how do you know how far to go with your sieve? Thanks again. \$\endgroup\$ – Avrohom Yisroel Jan 27 '16 at 18:33
  • \$\begingroup\$ Just realised that you can improve your potentialPrimes function a little bit more by observing that every prime (other than 2 and 3) is of the form 6n+/-1. Don't know how well it will come out in these silly little comments, but a slightly faster version of the function is as follows... let potentialPrimes =\n let rec SixNPlusMinus1 n = seq { yield (n-1); yield (n+1); yield! SixNPlusMinus1 (n+6)}\n seq { yield 2; yield 3; yield! SixNPlusMinus1 6}\n ... where I've added a \n to show where the new lines go \$\endgroup\$ – Avrohom Yisroel Jan 27 '16 at 18:59
  • 1
    \$\begingroup\$ @AvrohomYisroel A simple way to use a sieve for an nth prime question is just to find a maximum bound for the nth prime (there are algorithms online) and sieve up to that bound. You can do algorithmically better than that with more math and avoid sieving entirely, FWIW, but that's likely a lot more work. \$\endgroup\$ – Veedrac Jan 27 '16 at 19:44
  • 1
    \$\begingroup\$ @AvrohomYisroel You can make a lot of similar improvements to potentialPrimes, though the improvements tend to be relatively small (certainly not nearly enough to give a factor 10 improvement). \$\endgroup\$ – Veedrac Jan 27 '16 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.