Project Euler Problem 7: Find 10001st prime number

Question

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 -> (isDivibleBy x y) || acc) false previousPrimes)
let getPrime n =
    let rec getPrimesInternal count num previousPrimes =
        match count with
        | 0 -> previousPrimes
        | _ -> let prime = isPrime num previousPrimes
               match prime with
               | true -> getPrimesInternal (count - 1) (num + 1) (num::previousPrimes)
               | false -> getPrimesInternal count (num + 1) previousPrimes
    match n with
    | n when n <= 0 -> 0
    | n -> List.head (getPrimesInternal (n - 1)  2 [2])


[<EntryPoint>]
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 < 2 -> false
    | 2 -> true
    | _ when n % 2 = 0 -> false // even numbers greater than 2
    | _ -> // odd numbers greater than 2
        let limit = int(sqrt(float(n)))
        let rec check i =
            i > limit || (n % i <> 0 && check (i + 2))
        check 3

let getPrimes n = 
    let rec getPrimeInternal found i = 
        if found >= 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))

[<EntryPoint>]
let main argv = 
    printfn "%i" (getPrime 10001)
    0 // return an integer exit code

Answer 1

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 -> …
| false -> …

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

Answer 2

Algorithmically, there are a few problems I can see.

1. Because the previousPrimes list is in 'reverse' order, you are checking for divisibility starting with the least likely divisor to the most likely divisor. Half the integers are divisible by 2, a third divisible by 3, etc. So an earlier exit from Seq.exists will happen if you iterate [2;3;5;7...]

2. You don't need to test all previousPrimes, only those up to the square root of x.

3. Most of the time is spent dealing with the previousPrimes list (iterating, appending, etc.). While certainly it is correct that you only need to test prime divisors, a more naive tail-recursive isPrime function actually performs better:

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

Getting rid of previousPrimes and using the above primality test function, the performance improves 3 orders of magnitude.

Answer 3

Approaching this task I'd follow "functional first" principle, then bother about performance. The solution may be as simple as:

let projectEuler7() = primes |> Seq.nth 10001

or a mere direct F# translation of original problem "Of sequence of prime numbers take 10001th member".

Now the problem is a bit simpler: effectively and lazily generate (a potentially infinite) sequence of prime numbers. Lets approach the derivative problem following the same "functional first" approach:

let rec primes =
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
// We do cache the results for performance as we reuse already found primes
and nextPrime n = if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
// obvious; our only leftover problem is effectively determine if arbitrary n is prime
and isPrime n =
    primes
    |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
    |> fun x -> x.Value * x.Value > n
// implement the obvious zero reminder condition amplified by square root limit

That's it! 8 lines of functional first code with not at all bad performance: on my modest laptop it delivers solution to the original problem in only 90ms. Maybe few times slower, than your final code, but way far ahead by succinctness and clarity.