# Problem 40 Solutions

## Solution 1

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

Back to problem