From: Yui NARUSE <redmine@...>
Date: 2010-09-10T17:44:26+09:00
Subject: [ruby-dev:42228] [Ruby 1.9-Feature#3814] 	Prime.prime?をC拡張にする

チケット #3814 が更新されました。 (by Yui NARUSE)


このアルゴリズムでも4秒になるんですねぇ。

で、prime.rb はかなり素朴なアルゴリズムなので、これに速度を求めるのがそもそもの間違いな気がします。
Pure Rubyでもまだまだ頑張る余地があるわけで、まずよりよいアルゴリズムを用いるべきでしょう。

また、どうせほとんどは false なのですから、まずいくつか確率的に判定してみるのもいいんじゃないですかね。
http://deztec.jp/x/05/faireal/faireal-7-03-index.html

なお、ほんとうに早いのが欲しいのでしたら、OpenSSL::BNを使うのが正解だと思うので、
これを使うようにしたほうがいいでしょう。
----------------------------------------
http://redmine.ruby-lang.org/issues/show/3814

----------------------------------------
http://redmine.ruby-lang.org