Skip to content

Instantly share code, notes, and snippets.

@YuRen-tw
Created May 13, 2018
Embed
What would you like to do?
FLOLAC 2018 0-3: Goldbach's conjecture
goldbach :: Int -> Maybe (Int, Int)
goldbach = listToMaybe . goldbachFull
where listToMaybe = foldr (const . Just) Nothing
goldbachFull :: Int -> [(Int, Int)]
goldbachFull n = mkPairs . filter isNegPrime . takeHalfN $ primes
where mkPairs = map (\p -> (p, n-p))
isNegPrime p = isPrime (n - p)
takeHalfN = takeWhile (\p -> p*2 <= n)
primes :: [Int]
primes = 2 : filter isPrime [3, 5 ..]
isPrime :: Int -> Bool
isPrime n | n <= 2 = n == 2
| otherwise = all notDivisor . takeSqrtN $ primes
where notDivisor p = mod n p /= 0
takeSqrtN = takeWhile (\p -> p^2 <= n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment