The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
primes :: [Int] primes = 2 : sieve primes [3,5..] where sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0] where (h, t) = span (< p*p) xs isPrime :: Int -> Bool isPrime n | n < 1 = False | otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]] filterPairs :: Int -> [Int] -> [Int] filterPairs p = filter test where test x = isPrime (read $ show x ++ show p) && isPrime (read $ show p ++ show x) candidates :: [[Int]] candidates = [[a, b, c, d, e] | a <- primes', let bs = filterPairs a $ dropWhile (<= a) primes', b <- bs, let cs = filterPairs b $ dropWhile (<= b) bs, c <- cs, let ds = filterPairs c $ dropWhile (<= c) cs, d <- ds, let es = filterPairs d $ dropWhile (<= d) ds, e <- es] where primes' = takeWhile (< 10000) primes main :: IO () main = print $ sum $ head candidates
$ ghc -O2 -o prime-pairs prime-pairs.hs $ time ./prime-pairs real 0m0.460s user 0m0.460s sys 0m0.000s