【Project EulerにRubyで挑戦シリーズ】問5:Smallest multiple

スポンサーリンク

今回の問題

Smallest multiple

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

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

書いた内容

2520 について整理

問題文にある通り、2520 は1から10までの整数の最小公倍数です。
ということで、問3でも使ったprime_divisionメソッドを使ってみると
2の3乗 × 3の2乗 × 5の1乗 × 7の1乗 = 2520
となることが分かります。

require 'prime'
p Prime.prime_division(2520)
#=> [[2, 3], [3, 2], [5, 1], [7, 1]]

2次元配列の各要素の配列 [n,e] は下記のとおりです。
n が レシーバ の素因数、e が n**e で レシーバ を割り切る最大の自然数 e

2520 は1から10までのすべての数字で割り切れないといけないので、下記の通り
各指数の e は n の累乗が10を越えない最大の自然数である必要があります。

  • 例) 2の3乗 = 8 は10以下、2の4乗 = 16 はオーバー
  • 例) 3の2乗 = 9 は10以下、3の3乗 = 27 はオーバー

これを踏まえて下記ステップで実装しました。

  1. 1から20までの素数をすべて求める
  2. 各素数の累乗が20を超えない最大の指数を求め、素数との累乗を算出
  3. 更にそれらを掛け合わせれば最小公倍数となる
require 'prime'
prime_factors_array = Prime.each(20).to_a # ステップ1

prime_factors_index_array = prime_factors_array.map do |n|
  index = 0
  loop do
    index += 1
    break if 20 < n ** (index + 1)
  end
  n ** index # ステップ2
end

puts prime_factors_index_array.inject(:*) # ステップ3
#=> 232792560

便利なメソッドがすでにあった

そもそも、自身と整数 n の最小公倍数を返す lcm メソッドがリファレンスにありました。
https://docs.ruby-lang.org/ja/latest/method/Integer/i/lcm.html

これをinjectメソッドと併用して畳み込み演算を行えば、primeライブラリを用いることもなく
非常に簡潔に書くことが出来ました。

puts [*1..20].inject(:lcm)
#=> 232792560

※Project Eulerのリポジトリ

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。