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
        table

    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.

Advertisements
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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s