51問目
http://projecteuler.net/index.php?section=problems&id=51
56003は3桁目と4桁目の数字を置き換えると、56003, 56113, 56333, 56443, 56663, 56773, 56993と7つの素数を構成する。同様に一部の数字を置き換えることで8つの素数を構成する数のうち、最小のものを求める。
何というか解きづらい問題で、コードを書き始めるまで、すごく時間がかかりました。できてみるとふつーのアルゴリズムなんですが。
それぞれの素数について、一部を置き換えた数を生成して、素数がどれだけあるか調べていきます。例えば56003であれば、以下のような数を生成して素数がいくつあるか調べます。
- 56103, 56203, .. , 56903(3桁目を置換)
- 56013, 56023, .. , 56093(4桁目を置換)
- 56113, 56223, .. , 56993(3桁目と4桁目を置換)
同じ数字が複数含まれる場合は、そのうち一部だけを置き換える場合と全部まとめて置き換える場合とがあるので、面倒です。
またムダを減らすため、閾値以下の数字だけを置き換えるようにしています。例えば今回の問題では8個の素数を生成しなくてはなりませんが、3以上の数字を置き換えても7個以下の素数しかできません。したがって2以下の数字(上の例では0)だけを置き換えます。
import Data.List main = print $ euler051 8 euler051 :: Int -> Integer euler051 n = head $ filter ((yieldsFamily n) . show) $ primes yieldsFamily :: Int -> String -> Bool yieldsFamily n p = any ((>= n) . length) $ map (family p) (indices n p) family :: String -> [Int] -> [String] family p is = filter (isPrime . read) [ repl p is c | c <- dropWhile (< p !! (head is)) "0123456789" ] repl :: String -> [Int] -> Char -> String repl s [] c = s repl s (i:is) c = (take i s) ++ c : drop (i+1) (repl s is c) indices :: Int -> String -> [[Int]] indices n p = concat $ map (init . comb) [ elemIndices d p | d <- take (11-n) "0123456789" ] comb :: [Int] -> [[Int]] comb [] = [[]] comb (n:ns) = map (n :) (comb ns) ++ comb ns primes :: [Integer] primes = 2 : filter isPrime [3..] isPrime :: Integer -> Bool isPrime x = all ((/= 0) . mod x) $ takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes