Project Euler 12,13

Haskell

Problem 12

http://projecteuler.net/index.php?section=problems&id=12


素直にn(n + 1) / 2を素因数分解する。



m = 500

primes = 2:[3,5..]
div_pow n p | mod n p /= 0 = (n, 0)

            | otherwise    = (\(n, e) -> (n, e + 1)) (div_pow (div n p) p)
factorize n (p:ps) | n == 1         = []

                   | n < p * p      = [ (n, 1) ]

                   | mod n p == 0   = (\(p:ps) (n, e) -> (p, e) :

                            (factorize n ps)) (p:ps) (div_pow n p)

                   | n > 0          = factorize n ps
num_divs n = product (map (\(p, e) -> e + 1) (factorize n primes))

main = print(head (filter (\n -> (num_divs n) > m)

            (map (\n -> div (n * (n + 1)) 2) [1..])))

しかし、nをそれぞれ素因数分解して、隣と掛け合わせて2で割ったほうが速い。



 -- 残りは上と同じ

fact n = factorize n primes

value f = product (map (\(p,e) -> p^e) f)
num_divs f = product (map (\(p, e) -> e + 1) f)

div_p (p, e) q | p == q    = if e > 1 then [(p, e - 1)] else []

               | otherwise = [(p, e)]

half f = concat (map (\g -> div_p g 2) f)
a = map fact [1..]

b = [ half (x ++ y) | (x, y) <- zip a (tail a) ]

main = print(value (head (filter (\f -> (num_divs f) > m) b)))

Problem 13

http://projecteuler.net/index.php?section=problems&id=13


多倍長整数を使うだけ。



s = "37107287533902102798797998220837590246510135740250\n"

 ++ "46376937677490009712648124896970078050417018260538\n"

    ...

 ++ "53503534226472524250874054075591789781264330331690"
atoi :: [Char] -> Integer

atoi s = read(s)

main = print(take 10 (show(sum [ atoi(line) | line <- (lines s) ])))