今回のプログラミングのお題は、最大公約数と最小公倍数。

以前に、確か、基本情報処理技術者試験のアルゴリズムの問題で、求める問題を解いたと思うんだけど、そのアルゴリズムは見事に忘れてしまいました\(^o^)/
その時は、Rubyじゃなくて擬似言語を手書きでゴリゴリ書いていたかなぁ。

とりあえず、お題はコチラ。

GCD and LCM

・20億以下の正の整数2つが与えられ、その最大公約数と最小公倍数をもとめよ。

ロジックを思案。


思いついたのは、

・まず、両方の数字の共通な素因数で分解。
・最大公約数は素因数の掛け合わせ。
・最小公倍数は、素因数の掛け合わせ×2数の分解残。

たぶん、これでいけそうな気がする。早速、Rubyでコードを書いてみました。
そうそう、分解する素数を求めるコードは、メソッドを定義する技を使ってみました。

def nextsosuu(i)
i = i + 1
j = 2
while i != j do
if i%j==0 then
i=i+1
j = 1 
end
j = j+1
end
return i
end

file = open("gcdlcm.txt")
while array = file.gets.split(/\s/)
for i in 0..1 do
array[i] = array[i].to_i
end
x = array[0]
y = array[1]
i = 2

mem = Array.new
while i<=x && i<=y
while (x%i != 0 || y%i != 0) && (i<=x && i<=y) do 
i = nextsosuu(i)
end
if i>x && i>y then
break
end
mem[mem.size] = i 
x = x/i
y = y/i
end
yakusuu = 1
mem.each do |now|
yakusuu = yakusuu * now
end
print(yakusuu," ",yakusuu * x * y,"\n")
end


なんとか、コード化できました!