# 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
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