エラトステネスの篩

エラトステネスの篩を実装してみる。

まずは100までで試してみる。

• 余りがゼロの数を取り除く。

*Main> filter (\x -> mod x 2 /= 0)[2..100]
[3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99]

• 自分自身は除く必要がないから、filterの条件に自分自身は取り除かない。

*Main> filter (\x -> if x==2 then True else mod x 2 /= 0)[2..100]
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99]

• これをつなげていく。

*Main> filter (\x -> if x==3 then True else mod x 3 /= 0) $ filter (\x -> if x==2 then True else mod x 2 /= 0) [2..100]
[2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97]

• さらにこれをつなげていく。

*Main> filter (\x -> if x==4 then True else mod x 4 /= 0) $ filter (\x -> if x==3 then True else mod x 3 /= 0) $ filter (\x -> if x==2 then True else mod x 2 /= 0) [2..100]
[2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97]

*Main> filter (\x -> if x==5 then True else mod x 5 /= 0) $ filter (\x -> if x==4 then True else mod x 4 /= 0) $ filter (\x -> if x==3 then True else mod x 3 /= 0) $ filter (\x -> if x==2 then True else mod x 2 /= 0) [2..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97]

• ここで四苦八苦、、、、。

このつなげていくときに、関数の形は同じでですが、定数が異なる部分をどのようにコーディングすれば良いのでしょうか？ よくわからなかったので、カウンタを持ち回るように一旦ペアにして、最後にペアから結果をとる実装にしてみました。

また、停止条件をどうするかが分からず、外から与えるコーディングにしてみました。

--
-- Sieve of Eratosthenes
--

sieve' :: Integer -> [Integer] -> [Integer]
sieve' = \y z -> filter (\x -> (if x == y then True else (mod x y /= 0))) z

-- sieve :: [Integer] -> [Integer]
-- sieve x
--  | null x        = x
--  | head x > 100  = x
--  | otherwise     = sieve (sieve' ((head x)+1) (tail x))

sieve2 :: (Integer, [Integer]) -> (Integer, [Integer])
sieve2 (x, ys)
--   | x >= 100  = (x, ys)
   | elem x ys = sieve2 (x+1, sieve' x ys) 
   | otherwise = sieve2 (x+1, ys)


sieve3 :: Integer -> (Integer, [Integer]) -> (Integer, [Integer])
sieve3 z (x, ys)
   | x >= z    = (x, ys)
   | elem x ys = sieve3 z (x+1, sieve' x ys)
   | otherwise = sieve3 z (x+1, ys)
     
sieve :: Integer -> [Integer]
sieve z = snd $ sieve3 z (2, [2..z])

*Main> sieve 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
*Main>