From: TOYOFUKU Chikanobu <nobu_toyofuku@...>
Date: 2007-06-07T18:11:32+09:00
Subject: [ruby-dev:30920] Integer#prime_division 	と Prime

  豊福です。

  ((2**17-1)**2).prime_division に比べて ((2**19-1)**2).prime_division
の時間が異様にかかるので調べたところ Integer#prime_division
の中の
  ps = Prime.new
から素数列を生成するのにコストがかかっていて、より単純な
  ps = (2..n)
を使う方が速くなるようです。
（実用には 2,3と ±1(mod 6) あたりを使うのがよいでしょうか）

  また Prime の initialize と succ もより単純にした

  def initialize
    @seed = 1
    @primes = []
  end

  def succ
    i = -1
    size = @primes.size
    while i < size
      if i == -1
        @seed += 1
        i += 1
      else
        prime = @primes[i]
        q,r = @seed.divmod(prime)
        if r != 0
          break if q <= prime
          i += 1
        else
          i = -1
        end
      end
    end
    @primes.push @seed
    return @seed
  end

の方が速くなるようです。
---
                        豊福
                        nobu_toyofuku@nifty.com