What is the 10001^{st} 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.

### Like this:

Like Loading...

*Related*

[…] reduces to a ridiculously simple problem, given that we’ve already solved problem 7. Comments RSS […]