Problem 50
http://projecteuler.net/index.php?section=problems&id=50
2から始まる系列、3から始まる系列、をリストにして、長いものから調べていく。遅い。
import Data.Array sieve a p | a!p == True = sieve (a // [ (m, False) | m <- b, a!m ]) (p + 1) | p * p > n = a | otherwise = sieve a (p + 1) where b = if p == 2 then [p*2,p*3..n] else [p*3,p*5..n] n = 10^6 is_prime = sieve (array (2, n) [ (k, True) | k <- [2..n] ]) 2 primes = filter (is_prime!) [2..n] que :: [Int] -> [Int] que (p:ps) = p:[ q + r | (q, r) <- zip ps (que (p:ps)) ] queue ps = reverse (takeWhile (\(_,m) -> (m < n)) (zip [1..] (que ps))) queues (p:ps) = (queue (p:ps)):(queues ps) a = queues primes max_n = fst (head (head a)) h [] n = (0, 0) h (p:ps) n | fst p == n = p | fst p > n = h ps n | otherwise = (-1, -1) g (x:xs) n | fst m == n = m:(g xs n) | otherwise = [] where m = h x n f :: Int -> [[(Int,Int)]] f n = (g a n):(f (n - 1)) main = print(head (filter (\a -> length a > 0) (map (filter (\p -> is_prime!(snd p))) (f max_n))))
Problem 51
http://projecteuler.net/index.php?section=problems&id=51
0,1,2のどれかが3個以上の数について調べる。ややこしい。
is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3..]) digits 0 = [] digits n = (digits (div n 10)) ++ [mod n 10] numerize a = foldl (\x y -> x * 10 + y) 0 a count [] e = 0 count (p:ps) e = if p == e then 1 + n else n where n = (count ps e) base :: Int -> [(Int,Int)] base n = f n 0 where a = digits n f n 3 = [] f n d = (if count a d >= 3 then g a d else []) ++ (f n (d + 1)) where h [] d = [[]] h (p:ps) d = [ [a] ++ b | a <- (if p == d then [0,1] else [0]), b <- (h ps d) ] g a d = map (\n-> (d, n)) (filter (\n -> mod n 10 == 0) (map numerize (filter (\b -> div3 (count b 1)) (h a d)))) where div3 n = n > 0 && mod n 3 == 0 is_valid (n,(d,b)) = length (filter is_prime [n,n+b..n+b*(9-d)]) == 8 a = filter is_valid (concat (map (\n -> map (\b -> (n, b)) (base n)) [1..])) main = print(fst (head a))
