LCM

PDFをダウンロード

入力値の最小公倍数を計算します。

入力/出力

x —

xは整数です。

y —

yは整数です。

lcm(x,y) —

lcm(x,y)は、xとyの最小公倍数を返します。

lcm(x,y)は、最小の整数値mです。このとき以下のようになる整数cおよびdがあるとします。

x×c＝y×d＝m

lcm(x,y)を計算するには、xおよびyの素因子分解を考慮します。

x = Π_i p_i^a_i y = Π_i p_i^b_i

ここで、p_iはxおよびyのすべての素因数です。Piが因子分解で発生しない場合は、対応する指数は0になります。lcm(x,y)_iが因子分解で発生しない場合は、対応する指数は0になります。lcm(x,y) は以下の式で求められます。

lcm(x,y) = Π_i p_i^{max(a_i, b_i)}

たとえば、12と30の素因子分解は以下のようになります。

12 = 2² ×³¹ ×⁵⁰ 30 =²¹ ×³¹ ×⁵¹

したがって、

lcm(12,30) = 2² ×³¹ ×⁵¹ = 60