[Haskell] 素数列を生成するアルゴリズム×3 / LiosK-free Blog

[Haskell] 素数列を生成するアルゴリズム×3

最近すっかりブログから離れていたので、リハビリがてらにメモ代わりのエントリー。

Haskellで素数の無限リストを生成する関数を3つほど作ったのでメモ。

primes1 = 2:f [3,5..] where f (x:xs) = x:f [y | y <- xs, mod y x /= 0]

primes2 = 2:filter f [3,5..]
    where f n = all ((/= 0) . (mod n)) (takeWhile ((<= n) . (^ 2)) primes)

primes3 = 2:f [3] [3,5..]
    where f (x:xs) ys = let (ps, qs) = span (< x^2) ys
                        in  ps ++ f (xs ++ ps) [z | z <- qs, mod z x /= 0]

primes2に関しては1000000個の素数 - HaHaHa! - haskellを、primes3に関しては誇大宣伝ではないエラトステネスの篩 - HaHaHa! - haskellをそれぞれ参考にした。

以下解説。

解説

primes1 = 2:f [3,5..] where f (x:xs) = x:f [y | y <- xs, mod y x /= 0]

もっとも単純なエラトステネスの篩の実装。関数fは探索リストを受け取り、その先頭の数を取り出しつつ、先頭の数で割り切れない数のリストを新たな探索リストとして自身を呼び出す。コードは美しいが、やっていることは既知の素数全てで試し割りをして素数判定しているだけなので、ものすごく遅い。

primes2 = 2:filter f [3,5..]
    where f n = all ((/= 0) . (mod n)) (takeWhile ((<= n) . (^ 2)) primes)

コードの書き方はやや違うが、実際の計算の内容自体はprimes1と大きくは変わらない。違うのは、既知の素数全てで試し割りをするのではなくて、既知の素数のうち目的の数の平方根よりも小さい素数で試し割りをする点。

primes3 = 2:f [3] [3,5..]
    where f (x:xs) ys = let (ps, qs) = span (< x^2) ys
                        in  ps ++ f (xs ++ ps) [z | z <- qs, mod z x /= 0]

これはWikipediaのエラトステネスの篩の頁に書いてある、探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。という特徴をうまく使ったパターン。探索リストの数のうち、現在の素数の2乗よりも小さいものは全て素数として判定して素数リストに加えている。探索リストの計算方法はprimes1と同じだが、一度に複数の素数を探索リストから取り出せる分、primes1よりも圧倒的に速い。

スポンサーサイト

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/139-88624b8e

LiosK-free Blog