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?
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