http://projecteuler.net/index.php?section=problems&id=60
Setが自由に使うのが難しい。しかたがないので、上限を倍々していく。とても遅い。
import qualified Data.Set as S min_sum n = min_s where is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) num_digits n = head (filter (\m -> 10^m > n) [1..]) cat n m = n * 10^(num_digits m) + m memo = f [ (p, q) | p <- takeWhile (<n) primes, q <- (takeWhile (\q -> q < p && p + q < n) primes), is_conn (p,q) ] S.empty where f [] s = s f (x:xs) s = f xs (S.insert x s) is_conn (m,n) = is_prime (cat m n) && is_prime (cat n m) is_connected p q = S.member (p,q) memo add_prime :: [[Int]] -> [[Int]] add_prime a = [ p:b | p <- takeWhile (<n) primes, b <- takeWhile (\e -> (head e) < p) a, sum(b) + p < n && is_valid p b ] where is_valid p e = all (is_connected p) (reverse e) a = foldr (\x y -> add_prime y) (map (\p -> [p]) primes) [1..4] limit_sum = if length a == 0 then 0 else sum (head a) min_s = foldr min limit_sum (map sum (takeWhile (\e -> (head e) < limit_sum) a)) main = print (head (filter (>0) (map min_sum a))) where a = 1000:[ n * 2 | n <- a ]