Skip to content

Project Euler Problem 50

November 28, 2011

Project Euler Problem 50 solution reuses my primes sequence from Problem 10 solution.

For diversity I came up with an imperative solution. First, take a sequence of prime candidates and turn it into an array. Then for each member of array try to build a sum of consecutive members to the right that is less, than 1000000. If along this process any intermediate sum is a prime and the member sequence length is greater, than current global max length, then record this next max length and correspondent sum value. After all members are checked return the global prime sum of lengthiest consecutive sequence of primes.

#nowarn "40"

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 primeArray = primes |> Seq.takeWhile ((>) 1000000) |> Seq.toArray 
let primeCount = primeArray.Length
let mutable sum = 0
let mutable length = 0
let mutable maxLength = 0
let mutable result = 0

for i = 0 to primeCount - 1 do
    sum <- primeArray.[i]
    length <- 1
    let mutable j = i + 1
    while j <= primeCount - 1 && sum < 1000000 do
        sum <- sum + primeArray.[j]
        length <- length + 1
        if isPrime sum then
            if length > maxLength then
                result <- sum
                maxLength <- length
        j <- j + 1

printfn "%d" result

Advertisements

From → Project Euler

Leave a Comment

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: