結城浩のHaskell日記 RSSフィード

2006-06-13

エラトステネスの篩 エラトステネスの篩 - 結城浩のHaskell日記 を含むブックマーク

何となくエラトステネスの篩。

primes = sieve [2..]
    where
        sieve (n:ns) = (:) n $ sieve $ filter (`cannotDivBy` n) ns
        n `cannotDivBy` k = n `mod` k /= 0

実行結果です。

*Main> take 10 primes
[2,3,5,7,11,13,17,19,23,29]
*Main> primes !! 1000
7927

追記:nobsunの「双子素数」のリスト内包表記がかっこいーなー。

primes = sieve [2..]
sieve (p:ps) = p:sieve [p'| p'<-ps, p' `mod` p /= 0]
s f g x = f x (g x)
twins = filter ((2==) . uncurry subtract) $ s zip tail primes
  • s f g x = f x (g x) の部分は、一つの引数xを複数箇所で使い回す高階関数を作っちゃうところがおもしろい。「○○をしたい」→「それをする高階関数は?」
  • filterに渡している部分適用((2==) . uncurry subtract)もおもしろい。
    • まず、Num => a -> a -> aであるsubtractをuncurryで(a,a)->aにしちゃう。これはzipの出力をsubtractで受け止めるため。
    • そしてその結果が2になるかどうかを調べる。ふうん。
トラックバック - http://haskell.g.hatena.ne.jp/hyuki/20060613