FLOLAC'18 prerequisite p3

goldbach.hs

-- Build prime number table would be much slower than performing prime tests,
-- since we check only x and n-x, and in most cases x < 10 (28.7% when n < 20000).

goldbach' :: Int -> Int -> Int -> [Int]
goldbach' n m1 m2 = filter (\x -> isPrime x && isPrime (n-x)) $ 3:5:[6+m1,12+m1..n-2]
    where isPrime x = null $ filter (\y -> x `mod` y == 0) [2..fsqrt x] -- expect x > 1
          fsqrt = floor.sqrt.fromIntegral

goldbach :: Int -> Maybe (Int, Int)
goldbach 4 = Just (2, 2) -- the only case 2 would showed up
goldbach n               -- expect n `elem` [4,6..]
    | null search = Nothing
    | otherwise   = let x = head search in Just (x, n - x)
    where search = case n `mod` 6 of 0 -> goldbach' n 1 5 -- (6k+1, 6k-1)
                                     2 -> goldbach' n 1 1 -- (6k+1, 6k+1)
                                     4 -> goldbach' n 5 5 -- (6k-1, 6k-1)
                                     otherwise -> []

-- main = print $ map goldbach [4,6..20000] -- takes 0.95 sec