素数を列挙する #2

前回の続き。

素数表の検索にバイナリサーチを使う

前回、素数の判定法としてはもっとも素直な「√n 以下の整数で割る」よりは割り算が少なくなると考え、素数表を使った「√n 以下の素数で割る」方法を実装してみた。ところが、列挙範囲の素数表が完成している場合であっても(つまり割り算は一度も行わない)、「√n 以下の整数で割る」方が速いという結果になった。

その原因は Array#include? を使った素数表の検索にあるのではないかと考え、今回は検索に「バイナリサーチ(二分検索)」を使ってみることにした。

(listprimes_binsearch.rb より)
def ($primes).binsearch(n)
  len = self.size
  first = 0
  last = len - 1
  while len > 0
    mid = first + len / 2
    v = self[mid]
    if n == v
      return true
    elsif n < v
      last = mid - 1
    else
      first = mid + 1
    end
    len = last - first + 1
  end
  false
end

結果として、Array#include? を使ったものより高速になったことはもちろん、(素数表が完成していれば)列挙する範囲によっては「√n 以下の整数で割る」ものよりも速くなった。とはいえ、やはり素数表を生成しながらの場合は、比較にならないほど遅い。

• listprimes_binsearch.rb

エラトステネスの篩

素数表の生成でもう少し速そうな方法を試してみることにした。有名な「エラトステネスの篩」だ。コードを以下に示す。

「√n 以下の素数で割る」版、「篩」版、そして「シンプルに √n 以下の整数で割る」版を実行してみた結果は以下のようになった。

[imac] mnbi% rm primes.txt
[imac] mnbi% time ./listprimes_binsearch.rb 100000 100
START (99991):
100003 (66)
100019 (66)
100043 (66)
100049 (66)
100057 (66)
100069 (66)
Elapsed: 0.000275
./listprimes_binsearch.rb 100000 100  17.60s user 0.02s system 100% cpu 17.601 total
[imac] mnbi% time ./listprimes_sieve.rb 100000 100
100003
100019
100043
100049
100057
100069
Elapsed: 0.019148
./listprimes_sieve.rb 100000 100  0.02s user 0.00s system 83% cpu 0.033 total
[imac] mnbi% time ./listprimes_simple.rb 100000 100
100003 (158)
100019 (158)
100043 (158)
100049 (158)
100057 (158)
100069 (158)
Elapsed: 0.00028
./listprimes_simple.rb 100000 100  0.01s user 0.01s system 89% cpu 0.020 total

「篩」版は確かに速いが、「シンプル」版はさらに速い。

もっとも、これは表示させる領域を大きな数を基点として「狭めて」いるから起きることだ。1 から 100000 までの範囲の素数を列挙するなら「シンプル版」の方が遅くなる。

一番、速いのは

範囲(それも比較的大きな数から始まるものを)を指定して列挙させる場合、速いのは「√n 以下の整数で割る」方法をシンプルに実装したものだ。2 から始まる素数表を生成する方式では、範囲の上限に至るまでのすべての素数を生成する分不利になる。

たとえば、画面に一定範囲にふくまれる素数を表示する(だけの)アプリを作るとしたら、素数表を作る方式は適さないことになる。画面に表示できる範囲は限られているのだから、素数表を(作って)保持しておくより、見えている分だけをシンプルな方法(√n 以下の整数で割る)で判定する方がずっと素早く表示できるはずだ。

関連リンク

• エラトステネスの篩 (Wikipedia:ja)
• 二分探索 (同上)

関連記事

• 素数を列挙する