Project Euler in F#: Problem 7

What is the 10001st prime number?

Once again, I started off trying the obvious, brain-dead, brute force solution.

module Problem7 =
    let isPrime n = {2L .. n |> float |> sqrt |> int64} |> Seq.forall(fun m -> n%m <> 0L)
    let primes = seq {1L .. System.Int64.MaxValue} |> Seq.filter(isPrime)
    let ans = Seq.nth 10001 primes

That worked (and it ran well within the project Euler time bound) but after reading Dustin’s awesome solution, I couldn’t just leave it at that.

module AlternateProblem7 =
    open System.Collections.Generic

    let reinsert (n : 'a) (table : #IDictionary<'a,'a list>) prime =
        let comp = n+prime
        table.Remove(n) |> ignore
        match table.TryGetValue comp with
        | false,_      -> table.[comp] <- [prime]
        | true,factors -> table.[comp] <- prime::factors

    let rec sieve n (table : #IDictionary<'a,'a list>) =
        seq { match table.TryGetValue(n) with
                | false,_ ->
                    table.[n*n] <- [n]
                    yield n
                    yield! sieve (n+1L) table
                | true,factors ->
                    factors |> List.fold (reinsert n) table |> ignore
                    yield! sieve (n+1L) table }

    let primes = sieve 2L (new Dictionary<_,_>())
    let ans = Seq.nth 10001 primes

I avoided writing something like his nice dictionary interface, to force myself to really re-implement and understand his solution; as a result, this solution is shorter but much less elegant and idiomatic. This code is a tiny bit faster, as a side effect of not going through his nice Dict interface but, considering the minuscule difference in speed, I’d take his beautiful solution over my kludge any day.

Project Euler in F#: Problem 7

One thought on “Project Euler in F#: Problem 7

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s