## Project Euler Problem 60 Solution

## Question

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.

## Haskell

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

Questions? Comments? Send me an email: z@chdenton.com