Haskell H99 Question 31

http://www.haskell.org/haskellwiki/99_questions/31_to_41
ある自然数が素数かどうかを求める問題。

まず、素数を求めるロジックを、「初期値が２以上で、初期値までの各自然数で割り切れないこと」、という最も単純なアルゴリズムで解いてみる。

簡単なロジックで

isPrime x
	|x <= 1		= False
	|otherwise	= calculatePrime 2
	where
		calculatePrime y
			| x == y 			= True
			| mod x y == 0 		= False
			| otherwise 		= calculatePrime (y+1)

書き方はHaskellっぽいけどなんか冗長なので、次にエラトステネスのふるい風に作ってみる。
ちなみに、
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

エラトステネスのふるい風

calcPrime :: [Int] -> [Int]
calcPrime [] = []
calcPrime (x:xs) = x : calcPrime (sift xs)
	where
		sift [] = []
		sift (y:ys)
			| mod y x == 0 	= sift ys
			| otherwise 	= y : (sift ys)
			
prime = calcPrime [2..]

isPrime' x = isIncluded prime
	where
		isIncluded [] = False
		isIncluded (y:ys)
			| x > y 	= isIncluded ys
			| x == y 	= True
			| otherwise = False

遅くてびっくりした。まあがりがり書いただけだからな。。
でも遅延評価を有効に使えているのでいいかな。

まずcalcPrime関数ではある自然数配列から素数を引っこ抜いてます。
１を与えると変な挙動になりそうだからやめてください。後で直します。

primeは素数の無限配列を返します。

そして、後は単純にisPrime'で調べている自然数が要素より小さくなったら終わり、という感じです。

書き疲れたので模範解答は省略。