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

Back to problem