エラトステネスの篩
エラトステネスの篩を実装してみる。
まずは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>