or1ko's diary

日々を書きます

エラトステネスの篩(ふるい)

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)と思って,変数名そのものから変えた.