Rubyで最小公倍数を求める 〜Rubyでオイラープロジェクトを解こう！Problem5

Problem 5 - Project Eulerより

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
2520は1から10の各数字で割り切れる数の中で最小のものである。
同様に1から20の全ての数字で割り切れる最小の数は何か。

素直に20より大きい数字を順に1から20で割って
割り切れるものを見つける

 def find_divisible(max)
   n = max
   loop do
     break n if divisible_all?(n, max)
     n += 1
   end
   n
 end

 def divisible_all?(number, max=10)
   1.upto(max) do |n|
     return false if number.modulo(n) != 0
   end
   true
 end

 t = Time.now
 find_divisible(20) # => 232792560
 Time.now - t # => 504.792946

500秒！
遅すぎる！
別のやり方ないかな

全ての数で割り切れるというのは…
要するに最小公倍数のことだよね？

最小公倍数 - Wikipediaより

二つの整数に対して、どちらの倍数にもなっている最小の自然数をいう。

じゃあその求め方は？

最小公倍数の計算には、最大公約数 GCD (Greatest Common Divisor) を用いて行う。どちらも 0 でない整数 a, b に対して、最小公倍数は、最大公約数 gcd(a, b) を用いて、

二つの数に限らず、より多くの数の最小公倍数を求めたい場合は、上記のlcm関数を入れ子にすればよい。

なるほどなるほど
じゃあこれを入れ子にして
1から20の全てを求めればいいんだな
最大公約数は割り算を繰り返せば求められそうだ

最小公倍数を使った版

 def find_divisible(max)
   case max
   when 2
     lcm(1, 2)
   else
     lcm(find_divisible(max-1), max)
   end
 end

 def lcm(a, b)
   a * b / gcd(a, b)
 end

 def gcd(a, b)
   a, b = b, a if a < b
   return a if b == 0
   _mod = a.modulo(b)
   if _mod == 0
     b
   else
     gcd(b, _mod)
   end
 end

 t = Time.now
 find_divisible 20 # => 232792560
 Time.now - t # => 0.000371

断然速いぞ！

Rubyのリファレンスをよく見たら…
Rationalという便利なライブラリーがあったのですね

require "rational"

def find_divisible(max)
  case max
  when 2
    2.lcm(1)
  else
    max.lcm(find_divisible(max-1))
  end
end

find_divisible 20 # => 232792560

あれ？Ruby1.9ではrequireも不要みたいな…