Problem 41 Solution

goldbachGT : Int -> Int -> Int -> List ( Int, Int )
goldbachGT low high limit =
    List.filter (\( x, y ) -> x > limit && y > limit)
        <| List.concatMap maybeToList
        <| List.map goldbach
        <| [min low (limit * 2)..high]


maybeToList : Maybe a -> List a
maybeToList x =
    case x of
        Nothing ->
            []

        Just y ->
            [ y ]


goldbach : Int -> Maybe ( Int, Int )
goldbach n =
    if isOdd n || n < 3 then
        Nothing
    else
        goldbach' n <| primesInRange 2 n


goldbach' : Int -> List Int -> Maybe ( Int, Int )
goldbach' n ps =
    case ps of
        [] ->
            Nothing

        p1 :: xs ->
            let
                ps' =
                    dropWhile (\y -> p1 + y < n) ps

                ps'' =
                    takeWhile (\y -> p1 + y == 0) ps'
            in
                case List.head ps'' of
                    Nothing ->
                        goldbach' n xs

                    Just p2 ->
                        if p2 + p1 == n then
                            Just ( p1, p2 )
                        else
                            goldbach' n xs


primesInRange : Int -> Int -> List Int
primesInRange low high =
    if high < low || high < 2 then
        []
    else
        dropWhile (\x -> x < low) <| primes high



-- find all primes up to n


primes : Int -> List Int
primes n =
    if n < 2 then
        []
    else
        eratos [2..n] []



-- sieve of Eratosthenes
-- remove all the the non-primes from a list


eratos : List Int -> List Int -> List Int
eratos candidates primes =
    case candidates of
        [] ->
            List.reverse primes

        x :: xs ->
            let
                cs =
                    List.filter (\y -> (y % x) /= 0) xs
            in
                eratos cs (x :: primes)


dropWhile : (a -> Bool) -> List a -> List a
dropWhile predicate list =
    case list of
        [] ->
            []

        x :: xs ->
            if (predicate x) then
                dropWhile predicate xs
            else
                list


takeWhile : (a -> Bool) -> List a -> List a
takeWhile predicate list =
    case list of
        [] ->
            []

        x :: xs ->
            if (predicate x) then
                x :: takeWhile predicate xs
            else
                list



-- The core library function Arithmetic.isOdd is not available
-- on elm-lang.org/try, so we'll recreate it here


isOdd : Int -> Bool
isOdd n =
    n % 2 /= 0


isPrime : Int -> Bool
isPrime n =
    if n < 2 then
        False
    else
        List.member n <| primesInRange 2 n

Back to problem