Problem 159

http://projecteuler.net/index.php?section=problems&id=159
mdrs(n) = max_{m*d=n}(mdrs(m) + mdrs(d))
まぁ、成り立つでしょ。

import Control.Monad
import Data.Array.IO
lim = 10^6
main = do 
  drs <- newListArray (2,lim-1).tail.cycle$[1..9] :: IO (IOUArray Int Int)
  let update n dn = forM_ [2..div (lim-1) n] $ \m -> do
                      dm <- readArray drs m
                      dmn <- readArray drs (n*m)
                      writeArray drs (n*m) $ max dmn (dn+dm)
  forM_ [2..div lim 2] $ \n -> 
       readArray drs n >>= update n
  getElems drs>>=print.sum.map toInteger

IOUArrayは偉大だ。IOArrayよりも10倍ぐらい速かった。