rubyで複数の値の最小公倍数と最大公約数を求める

Project EularをRubyを使用して解いているのですが、その5番目の問題が最小公倍数に関する問題でした。
http://projecteuler.net/problem=5

そこで複数の値の最小公倍数を求めるメソッドを作ってみました。

require 'prime'

class Integer
  # 素数指数表現
  def prime_decomposition
    result = Hash.new(0)
    primes = Prime.each(Float::INFINITY).lazy
    num = self

    div = 1

    while num / div != 0
      div = primes.next
      count = 0
      while num % div == 0
        num /= div
        count += 1
      end
      result[div] = count unless count.zero?
    end

    result
  end
end

class Array
  def lcm
    numerator = self.inject(:*)

    result = Hash.new(0)
    num = 1

    self.each do |num|
      tmp = num.prime_decomposition

      tmp.each do |key,value|
        result[key] = [result[key],value].max
      end
    end

    result.each do |key,value|
      num *= key**value
    end

    num
  end
end

渡された各数字の素数指数表現を出して、それぞれの素数の指数の最大を取って、最後に掛けあわせれば最小公倍数の出来上がり。素数指数表現を出すメソッドもついでに作ったのですが、割と使い勝手がいいです。

100.prime_decomposition       #=> {2=>2, 5=>2}
333.prime_decomposition       #=> {3=>2, 37=>1}
2000.prime_decomposition      #=> {2=>4, 5=>3}
123456789.prime_decomposition #=> {3=>2, 3607=>1, 3803=>1}

大きな値になるとすごく遅くなりますけどね。

これを使ってlcm(最小公倍数)メソッドを作成

[1,2,3].lcm     #=> 6
[4,5,6].lcm     #=> 60
[10,25,37].lcm  #=> 1850

ちゃんと動いています。

もっといい方法があった。

「複数の値の最小公倍数求めるメソッドが出来たぞー、しかもlazyメソッドとか使って2.0っぽい！」と満足していたのですが、調べているうちにもっといい方法がありました。ついでに最大公約数を求めるメソッドも出来ました。

class Array
  def lcm
    self.inject{|a,b| a.lcm(b)}
  end

  def gcd
    self.inject{|a,b| a.gcd(b)}
  end
end

[1,2,3,4].lcm        #=> 12
[2,4,5,9].lcm        #=> 180
[120,50,15].gcd      #=> 5
[14000,2000,200].gcd #=> 200

これで完成です。コードも短くて非常にシンプルです。僕が作ったのは忘れて下さい。injectメソッドが便利すぎる。

*追記(2014/04/20)

実は上のコードinjectメソッドにシンボル渡すだけでよかったみたいです。

class Array
  def lcm
    inject(:lcm)
  end

  def gcd
    inject(:gcd)
  end
end

恐るべしinject

参考ページ

「Rubyで最小公倍数を求める ～Rubyでオイラープロジェクトを解こう！Problem5」
http://d.hatena.ne.jp/keyesberry/20090115/p1

「Ruby:覚書（最大公約数を求めるメソッド）」
http://wind-akagi.blogspot.jp/2011/01/ruby_21.html

「Primeクラス」
http://doc.ruby-lang.org/ja/1.9.3/class/Prime.html

「3つ以上の整数の最大公約数・最小公倍数を計算するRubyプログラムの例」
http://yoshiiz.blog129.fc2.com/blog-entry-192.html