Problem 3

http://projecteuler.net/index.php?section=problems&id=3

13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

素因数分解だけど素数列は不要。小さい数から繰り返し割っていけば素数以外は因数にならないので。

Float::INFINITY 使ってないのに break 使ってるので、なんか負けた気はしている。

class Integer
  def factorization(x)
    [].tap{|t| (0..Float::INFINITY).inject(self){|r,i|
        break if r==1
        r%x==0 ? (t << x; r/x) : (t << r; 1)
      }
    }
  end
  def prime_factorization
    [].tap{|t|
      (2..self).inject(self){|r,i|
        f=r.factorization(i)
        if f[-1]==i then    # i で最後まで割り切った
          t.concat(f)
          break
        elsif f[-2]==i then # i で割れたけどまだ残りがある
          t.concat(f[0..-2])
          f[-1]
        else                # i で割れなかった
          r
        end
      }
    }
  end
end

p 600851475143.prime_factorization.tap{|t| p t}[-1]