問題 1: リストを使ってはいけない.

10 未満で 3 もしくは 5 の倍数である自然数をすべて列挙すると,3,5,6,9 で,その和は 23 である.1000 未満の 3 もしくは 5 の倍数の和を求めよ.

Haskellだと数列を表現するリストやフィルタが簡単に書けてしまうので,以下のようにやってしまいがちなのだが,...

main :: IO ()
main = print $ p0001 1000

p0001 :: Integer -> Integer
p0001 n = sum [ x | x <- [1..n-1], x `mod` 3 == 0 || x `mod` 5 == 0 ]

もちろん,これは「正しい」ことが明らか.この問題では1000未満と範囲が狭いのでたいしたことはないけれど,これが10^10未満という問題だったらどうか.範囲内の数をすべて生成してから,フィルタをかけて,それから和を求めるなんてのはすこし脳天気ですよね.「あなた,効率というものを考えたことないでしょ.」と諭されることになりそう.n以下の自然数の和は n に関して閉じた式があるのだから以下のようにしよう.

s :: Integer -> Integer
s n = n*(n+1) `div`  2 

sm :: Integer -> Integer -> Integer
sm m n = m*s (n'`div`m)
  where n' = n - 1

p0001 n = sm 3 n + sm 5 n - sm 15 n