Project Euler 77

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

Haskellなら簡単に書ける。

n = 5000
is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes)
primes = 2:(filter is_prime [3,5..])

mul f p = [ g f k 0 | k <- [0..] ] where
        g (x:xs) k m | k < m     = 0
                     | otherwise = (if mod (k - m) p == 0 then x else 0)
                                    + (g xs k (m + 1))

update a (p:q:ps) | (a!!p) > 5000 = p
                  | otherwise     = update (mul a q) (q:ps)
main = print (update (1:[0,0..]) (1:primes))