Enumerator::Lazy でエラトステネスの篩

Enumerator::Lazy は無限数列を扱うことができるが、それを使って「エラトステネスの篩」をちょっとおもしろく実装できることに気づいた。何はともあれコードである。

lazy_prime.rb

prime_seq = Enumerator.new do |y|
  sieve = 2.step.lazy
  loop do
    a = sieve.first
    y << a
    sieve = sieve.reject {|x| (x % a).zero?}
  end
end

prime_seq.take(10)    #=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

　
Enumerator::Lazy はsieve = 2.step.lazyのところで生成している。これの先頭aは必ず素数なので、素数列として Enumerator で取り出す（y << a）。そして、sieveからaの倍数をrejectですべて篩い落とし（Lazy だから可能なのである）、そうされたものを新しいsieveとする。以下、繰り返し、というわけである。

これは子供の頃に紙と鉛筆でやってみた「エラトステネスの篩」のやり方そのものである。小さい方から素数に丸でも打っておいて、その倍数を斜線で消していく…。実装としては、素直といえば素直だ。

しかし、これ、めちゃめちゃに遅いのはすぐわかる。素数ひとつ得るたびに、Enumerator::Lazy オブジェクトを作り直しているのだから、どれほど遅いかというと、例えば最初の 500個の素数を得るのに、この方法だとわたしの環境でなんと 2.8秒ほどもかかる。標準添付ライブラリの prime を使うと 0.0002秒ほどだから、比較にもならない。

でもまあ、ちょっとおもしろかったので書いてみた。

なお、単なる Enumerator ももちろん無限数列を扱うことができるが、mapやselect、それにここで使ったrejectなどの結果が有限数列（Array）になってしまう。なので、Enumerator::Lazy を使ったのである。為念。

以上はブログ記事の転載です。