Project Euler 10,11

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.List
l = 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 a
cat 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 ])