Saturday, May 8, 2010

Problem 7: What is the 10001st prime number?

I think I’m getting the hang of this!  Some notable optimizations: isPrime only needs to check the divisibility of n by numbers 2..sqrt(n), and nthPrime only needs to check odd numbers for primality by incrementing i by steps of 2 starting at 1.

let problem7a =
    let isPrime n =
        let nsqrt = n |> float |> sqrt |> int
        let rec isPrime i =
            if i > nsqrt then true
            elif n % i = 0 then false
            else isPrime (i+1)
        isPrime 2
        
    let nthPrime n = 
        let rec nthPrime i p count =
            if count = n then p
            elif i |> isPrime then nthPrime (i+2) i (count+1)
            else nthPrime (i+2) p count
        nthPrime 1 1 0
        
    nthPrime 10001

No comments:

Post a Comment