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番目の素数だけ妙に遅い。おかしいな。