Ruby - 素数クラスで遊んだ話
RubyのPrimeクラスを使ったことがなかったから、いろいろ動かしてみた。
バージョンは2.1.2です。
n以下の素数の配列
class Prime def self.list(upper_bound) Prime.each(upper_bound).map(&:to_i) end end Prime.list(11) #=> [2, 3, 5, 7, 11] Benchmark.bmbm do |x| x.report("10 ** 8"){p Prime.list(10 ** 8).size} end //10 ** 8 4.620000 0.030000 4.650000 ( 4.651467)
eachを使ってみたかっただけ。to_iをがりがりやってるから遅いだろうと思ったら、普通に速度が出る。
to_iを使わないようにするとこんな感じ
class Prime def self.list(upper_bound) generator = Prime::EratosthenesGenerator.new list = [] loop do num = generator.next return list if num > upper_bound list << num end end end Benchmark.bmbm do |x| x.report("10**8"){p Prime.equal_or_more_than(10 ** 8).size} end //10 ** 8 3.390000 0.040000 3.430000 ( 3.439125)
Primeクラス使わずに自作して、どのぐらい遅いか比較しようかと思ったけど、勝てないので止めた。
勝てるようなやつ書きたいと思った。
n以上の最小の素数
class Prime def self.equal_or_more_than(n) generator = Prime::EratosthenesGenerator.new loop do num = generator.next return num if num >= n end end end Benchmark.bmbm do |x| x.report("10**8"){p Prime.equal_or_more_than(10 ** 8)} end //10**8 2.860000 0.000000 2.860000 ( 2.857946)
何も考えず書いたコード。この速度じゃRSA暗号には使えない。
n番目の素数
class Prime def self.at(n) generator = Prime::EratosthenesGenerator.new (n - 1).times{ generator.next } generator.next end end Benchmark.bmbm do |x| x.report("at 10**7"){p Prime.at(10 ** 7)} end //at 10**7 4.870000 0.000000 4.870000 ( 4.867939)
Prime::EratosthenesGeneratorを使ってみたかっただけ。
n以下の素数の数
class Prime def self.count_equal_or_less_than(n) generator = Prime::EratosthenesGenerator.new count = 0 loop do num = generator.next return count if num > n count += 1; end end end Benchmark.bmbm do |x| x.report("10**8"){p Prime.count_equal_or_less_than(10 ** 8)} end //10**8 3.150000 0.000000 3.150000 ( 3.149364)
関連して、素数定理の近似。
π(n) / (n / logn)
def approximation(n) Prime.count_equal_or_less_than(n) / (n / Math.log(n)) end p approximation 10 ** 8 //1.0612992317564809
あれ、n番目の素数だけ妙に遅い。おかしいな。