Problem21 -友愛数の和-

Haskell 30分プログラム

30分プログラム、その287。Problem21 via Project Euler。

d(n)をnの真の約数の和と定義する。（真の約数とはn以外の約数のことである。）
もし、d(a) = b かつ d(b) = a を満たすとき、aとbは友愛数（親和数）であるという。
例えば、220の約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110なのでd(220) = 284とである。
また、284の約数は1, 2, 4, 71, 142なのでd(284) = 220である。
それでは10000未満の友愛数の合計を求めよ。

Project Eulerのようなクイズ系に、Haskellは反則なイメージがある。でも、最近Haskellを使っていないので、Haskellで解いてみた。多少時間がかかるものの、力技で解けてしまった。やっぱり、反則だと思う。

あと、日本語訳のページに誤字があったので、修正しといた(100->110)。

# ところで、友愛数といえば、"博士の愛した数式"ですよね?

使い方

$ time ./problem21
40284
./problem21  26.04s user 0.57s system 93% cpu 28.492 total

ソースコード

友愛数がfriendじゃないと知ったのは、コード書いたあとだったのです。amicable numbersですって。

module Main where
divisor :: Int -> [Int]
divisor n = filter (\x->n `mod` x == 0) [1..n-1]

-- x `friendWith` y = (sum $ divisor x) == y && (sum $ divisor y) == x

hasFriend x = let friend = sum $ divisor x in
              x == (sum $ divisor friend)

solve = sum $ filter hasFriend [1..10000-1]

main = print solve

参考