エラトステネスの篩(ふるい)
wikipedia:エラトステネスの篩
を実装してみた.
main = print $ era [] $ step1 100 step1 n = [2..n] step2 ps ns = ps ++ [head ns] step3 ps ns = filter (\n -> (mod n (last ps)) /= 0) ns era [] ns = era (step2 [] ns) $ step3 (step2 [] ns) ns era ps [] = ps era ps ns = if (last ps) * (last ps) >= (last ns) then ps ++ ns else era (step2 ps ns) $ step3 (step2 ps ns) ns
step1を無限リストにすると,Vistaの調子が悪くなる.
take 10 $ era [] [2..]
といったように書くにはどうしたらいいのだろうか.
追記:searchsはひどい(せめてsearches orz)と思って,変数名そのものから変えた.