読者です 読者をやめる 読者になる 読者になる

or1ko's diary

日々を書きます

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

Haskell
take 10 $ era [] [2..]

といったように書くにはどうしたらいいのだろうか.
と思っていたので,書き直してみた.

import Data.List (findIndex)

plist :: [Int]
plist = era [2..]

era :: [Int] -> [Int]
era [] = []
era (p:ns) = [p] ++ ps ++ (era ns''')
	where
		ns' = filter (\n -> 0 /= mod n p) ns
		(ps, ns'') = maybe ([],[]) (\i -> splitAt i ns') $ findIndex (p*p <) ns'
		ns''' = filter (\n -> not $ any (\n' -> 0 == mod n n') ps) ns''

main :: IO ()
main = print $ last $ take 10001 $ plist

wikipedia:エラトステネスの篩

エラストステネスのステップ4をどうしようかと考えたすえ,findで探すことにした.
findを使ってることと無限リストを対象にしてるせいか,もとの奴より遅い.