Skip to content

Project Euler Problem 10

October 12, 2011

Project Euler Problem 10 turns to prime numbers again. After considering for some time of reusing solution to the Problem 7 I finally decided that having duplication of primes list and prime sequence is a way ugly and having just one collection of primes should be good enough!

The sequence of integer prime numbers uses already found numbers to unfold new ones. The heart of the prime generator is isPrime: int -> bool function that scans sequence of already found prime numbers checking for either zero division reminder, or reaching sequence member, which square is greater, than function argument. If second check is true, then the argument is (new) prime. To speed things up the sequence of primes is cached. Interesting, that this is the first time that I have a need for three function/data pieces combined with and.

As to the solution beyond generation of prime numbers sequence, it is straightforward: of all primes take those that less 2000000 and aggregate them into a sum.

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

let problem010 () =
    primes
    |> Seq.takeWhile ((>) 2000000)
    |> (Seq.map int64 >> Seq.sum)
Advertisements

From → Project Euler

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

%d bloggers like this: