Rubyでコードを書いてみた〜序の6〜

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

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

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

GCD and LCM

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

ロジックを思案。


思いついたのは、

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

たぶん、これでいけそうな気がする。早速、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

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