素因数分解

昨日は素数をやったので，今日はそれを使って素因数分解をしました．
とりあえず，こんなんです．特に変な事はしてません．

class Integer
  def prime?
    return false if self < 2
    (2 ... self).each{|x|
      # 割り切れたら素数じゃない
      return false if self % x == 0
    }
    true
  end
  
  def  factor
    primes = []
    # 素数なら配列に突っ込んで返す
    return primes.push(self) if self.prime?
    # 1以下の数なら素因数分解出来ないので空の配列を返す
    return primes if self < 2
    
    n = self
    # 2から順番に，素数で割っていく
    (2 ... n).each{|p|
      if p.prime?
        while n % p == 0
          primes.push(p)
          n = n / p
        end
      end
      break if n == 1
    }
    primes
  end
end

実際にirbで試してみます．

> 18.factor
=> [2, 3, 3]
> 256.factor
=> [2, 2, 2, 2, 2, 2, 2, 2]
> 2314521.factor
=> [3, 3, 3, 11, 7793]

最後のは，変に時間がかかりました．普通に繰り返し処理ってのは重たいもんなんですね．たぶん．こーゆー関数は，コンパイルしてバイナリにしてやらないと処理がキツいかも．柔軟性を考えたら総当たりじゃないといけないからなぁ．ちなみに，ウチの環境では

30923475.factor

が，なかなか帰ってきません．コマンドラインから実行できるfactorなら一瞬なんですけどね．