Project Euler 92

Haskell

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


1000までは1か89になるまで辿って89になればSetに入れる。それより大きい場合は1000以下になるまで辿る。この問題の範囲内では1回で1000以下になるはず。

import qualified Data.Set as S

digits :: Int -> [Int]
digits 0 = []
digits n = (digits (div n 10)) ++ [mod n 10]
next :: Int -> Int
next n = sum (map (^2) (digits n))

f 89 = True
f  1 = False
f  n = f (next n)

s = S.fromList (filter f [1..1000])

f2 n | n <= 1000 = S.member n s
     | otherwise = f2 (next n)

n = 10^7
main = print (length (filter f2 [1..n-1]))