Skip to content

Instantly share code, notes, and snippets.

@redbug312
Last active May 11, 2018
Embed
What would you like to do?
FLOLAC'18 prerequisite p3
-- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment