Project Euler Problem 7: Find 10001st prime number I was able to complete the problem, but I would like to improve my code and make it more idiomatic. 

Here is the challenge description:


  Problem 7 - 10001st prime
  
  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 10 001st prime number?
  
  http://projecteuler.net/problem=7


Here is my code:

let isDivibleBy num denum = num % denum = 0
let isPrime x previousPrimes = not (Seq.fold (fun acc y -&gt; (isDivibleBy x y) || acc) false previousPrimes)
let getPrime n =
    let rec getPrimesInternal count num previousPrimes =
        match count with
        | 0 -&gt; previousPrimes
        | _ -&gt; let prime = isPrime num previousPrimes
               match prime with
               | true -&gt; getPrimesInternal (count - 1) (num + 1) (num::previousPrimes)
               | false -&gt; getPrimesInternal count (num + 1) previousPrimes
    match n with
    | n when n &lt;= 0 -&gt; 0
    | n -&gt; List.head (getPrimesInternal (n - 1)  2 [2])


[&lt;EntryPoint&gt;]
let main argv = 
    printfn "%i" (getPrime 10001)
    0 // return an integer exit code


One of the major problem I would like to address is performance.  An easy way to improve the performance would be to stop the fold when a prime number is found, but I couldn't find the appropriate technique or function.

Updated version of code:

let isPrime n =
    match n with
    | _ when n &lt; 2 -&gt; false
    | 2 -&gt; true
    | _ when n % 2 = 0 -&gt; false // even numbers greater than 2
    | _ -&gt; // odd numbers greater than 2
        let limit = int(sqrt(float(n)))
        let rec check i =
            i &gt; limit || (n % i &lt;&gt; 0 &amp;&amp; check (i + 2))
        check 3

let getPrimes n = 
    let rec getPrimeInternal found i = 
        if found &gt;= n
        then []
        else 
            if isPrime i
            then i::getPrimeInternal (found + 1) (i + 1)
            else getPrimeInternal found (i + 1)
    getPrimeInternal 0 2

let getPrime n = 
    Seq.last (List.toSeq (getPrimes n))

[&lt;EntryPoint&gt;]
let main argv = 
    printfn "%i" (getPrime 10001)
    0 // return an integer exit code
One of the major problem I would like to address is performance.


When thinking about performance, the first question you should ask yourself is: could I use a better algorithm? Turns out there are better algorithms for generating primes, though they would be more difficult to implement (especially since they find all primes up to a certain number, which is not the same as finding the n-th prime).

It's probably not worth it in this case.


  An easy way to improve the performance would be to stop the fold when a prime number is found


You can use Seq.exists for that, which will also make your code simpler:

let isPrime x previousPrimes = not (Seq.exists (isDivibleBy x) previousPrimes)


(I'm using partial function application instead of a lambda, to make the code shorter.)



Other notes:

let isDivibleBy num denum = num % denum = 0


I think this function should be called isDivisibleBy.

match prime with
| true -&gt; …
| false -&gt; …


This is what if is for.

 getPrimesInternal count (num + 1) previousPrimes


If you start with num = 3 (and not 2), you can be sure that all primes that you test will be odd, so you can use num + 2 here, speeding up your code by about 50 %.