Problem 10
http://projecteuler.net/index.php?section=problems&id=10
200万までの素数を出さなければならない。
n = 2000000
is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) (2:[3,5..]))
main = print(sum (filter is_prime [2..n-1]))
ここでは素数判定に2,3,5,7,...という整数を使っているが、次のようにすると素数のみで素数判定ができる。
n = 2000000
is_prime m = all (\p -> mod m p /= 0) (takeWhile (\p -> m >= p * p) primes)
primes = 2:[ m | m <- [3,5..n ], is_prime m ]
main = print(sum primes)
Problem 11
http://projecteuler.net/index.php?section=problems&id=11
これを横に並んだ数のリストのリスト（これを行列と考える）と考えれば、横の並びの積を求めるのは簡単。
縦の並びの積を求めるには、行列を転置する。これは、Data.Listに用意されている。
斜めの積を求めるのには、斜めの並びのリストを作る。lower_leftが左下半分の斜めの並びの作る関数。右に行くにしたがって列を1つ上げるイメージ。
1 2 3 5 6 9
4 5 6 -> 8 9 ->
7 8 9
それぞれの行の先頭を取ると、[ [1,5,9], [4,8], [7] ]となる。
転置すれば左上半分のリストが求められるし、行列を反転すれば直交するリストが得られる。
linesは改行で区切った文字列のリスト、wordsは空白文字で区切った文字列のリスト。
import Data.Listl = 4
str = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n"
++ "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n"
...
++ "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\n"mul a = foldr (\x y -> x * y) 1 a
max_product [] n = 0
max_product a n = max (mul (take n a)) (max_product (tail a) n)
max_product2 a = foldr (\x y -> max (max_product x l) y) 0 acat a b = map (\(x,y) -> x ++ y) (zip a b)
lower_left a | length (head a) == 1 = a
| otherwise = cat (map (\x -> [head x]) a)
(lower_left ((map tail (tail a))) ++ [[]])a :: Int
a = map (\s -> map read (words s)) (lines str)
b = transpose a
c = reverse a
d = transpose c
e = lower_left a
f = lower_left b
g = lower_left c
h = lower_left d
max_a = max_product2 a
max_b = max_product2 b
max_e = max_product2 e
max_f = max_product2 f
max_g = max_product2 g
max_h = max_product2 h
main = print(foldr max 0 [ max_a, max_b, max_e, max_f, max_g, max_h ])
