Problem 5

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

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。
では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

1から20までの数を素因数分解して、素因数ごとの最大の指数を求める。

Problem 3 で作った Integer#prime_factorization を再利用。

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 (2..20).map{|i|
  i.prime_factorization
}.inject([]){|r,i|
  r+i.group_by{|ii| ii}.map{|k,v| v}
}.group_by{|i| i[0]}.map{|k,v|
  v.max
}.flatten.inject(:*)

解き終わったのがまだあるけど、まとめるのがめんどくさいので今日はここまで。