CodeIQ：通分と約分を実装しよう

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「通分と約分を実装しよう」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

小学生が分数を学ぶときに、最初に躓くのが「通分」です。
分母の異なる分数の足し算や引き算を行うとき、先に通分を行っておく必要があります。
また、計算した結果、「約分」できる場合は、可能な限り簡単な分数にしないと正解になりません。

【問題】
では、入力される二つの分数について足し算を行った時に、正しい答えを出力するプログラムを作ってください。
計算途中で32bitを越えることはないものとします。
※分母が１の時には整数として出力してください。

【入出力サンプル】
例1）
標準入力

5/6
1/10

標準出力

14/15

例2）
標準入力

1/3
2/3

標準出力

1

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

require 'prime'

def add(v1, v2)
	return [v1[0]*v2[1]+v2[0]*v1[1], v1[1]*v2[1]]
end

def reduce(v)
	n = v[0]	# 分子
	d = v[1]	# 分母
	Prime.each{|r|
		if (r>n) || (r>d) then break end
		while (n%r==0) && (d%r==0)
			n /= r
			d /= r
		end
	}

	return [n,d]
end

def printResult(v)
	if v[1] == 1 then puts v[0]
	else printf("%d/%d\n", v[0], v[1])
	end
end

# main
# Rationalを使えば独自実装の必要はないが、さすがに反則と思うので
inputs = []
while line = gets
	line.strip!
	if line.empty? then next end

	inputs << line.split("/").map{|a| a.to_i}
end

v = add(inputs[0], inputs[1])
v = reduce(v)
printResult(v)

解説

特に難しいことはありません。
コメントにも書いてありますがRubyの場合Rationalを使えば自分で実装する必要すらありませんが、さずがにそれはどうかと思ったので足し算と約分を自力で実装しました。

考え方

小学校で習った通りにやるだけです。
足し算は、a/b+c/d=(ad+bc)/(bd)、です。

約分の方がちょっと難しいですが、そう大したことはありません。
足し算の結果をn/mとするとnとmを共に割り切れる素数で延々と割って行けばできます。

add()

足し算を行います。引数v1、v2は[分子,分母]の配列です。
あとは考え方の通りの値を計算して返します。
返り値も[分子,分母]の配列です。

reduce()

約分を行います。引数vは[分子,分母]の配列です。
あとは考え方の通りに素数でずっと割り続けます。
問題はブレーク条件ですが単純に素数がm'、n'（m'、n'は共に割り切れる素数で割った結果の値）より大きくなったらにしています。
返り値も[分子,分母]の配列です。

printResult()

約分を行います。引数vは[分子,分母]の配列です。
仕様に合わせた印字を行います。
分母が1の時は分子だけを、そうでなければ"分子/分母"を表示します。

雑感

どうこう言うような問題ではありません。
でも、このプログラムの約分の性能（速さ）はどうでしょう？ 32bit整数くらいなら一応大丈夫と思うのですが、分母分子共に最大値に近い素数だったとしても間に合うでしょうか？