RubyでProject Euler - Problem 5

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?

電卓を使っても答えは簡単に出ますが、コードを書く段になってはたと手が止まりました。

結局は、初期値1とした変数を１から20までの数との最小公倍数で逐次更新していくことに気づくと一気に解決します。

とは云っても最小公倍数を求めるメソッドを知らなければ、さほど簡単ではありません。件のライブラリ「mathn (raitonal)」をrequireすれば、最小公倍数を算出するメソッド"lcm"を使うことができるようですが、ここは自前で書きました。答えの数値は簡単に求められますから、コードを伏せても意味はありませんね。injectも使わないし、相変わらずRuby的じゃないけど、書いたコードを載せておきます。

最大公約数を算出するメソッドも併せて必要になります。

それにしても、ユークリッドさんはえらいなぁ…とつくづく思います。

  def my_lcm(m, n) # m,mの最小公倍数を返す
    p = my_gcm(m, n)
    p * (m / p) * (n /p)
  end

  def my_gcm(m, n) # m,mの最大公約数を返す
    return my_gcm(n, m) if m < n
    p = m % n
    return n if p == 0
    my_gcm(n, p)
  end

  answer = 1
  (1..20).each do |x|
    answer = my_lcm(answer, x)
  end
  puts answer

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。