前回の続き。

$6$ と $15$ の最小公倍数・最大公約数を求めます。

考えたアルゴリズム

要素の数が2つなら、最大公約数と最小公倍数の関係*1から、どちらかを求めればもう一方は算出できます。

が、今回は、2つ以上としているのでそうはいきません。

プログラミングでの実装しやすさも踏まえて、以下の手順としました。

各要素の値ごとに、素因数分解

$6 = 2^{1} \times 3^{1}$

$15 = 3^{1} \times 5^{1}$

素数を覚えていれば楽だけど、プログラミングの時には先に何が素数かを求めるべきか否か？

また、素因数分解もどういう手順で考える必要あり。

次の手順で指数を並べるので、通常は指数が $1$ の時は $1$ を省略するけれど、敢えて省略せずに記載しました。

なので、 $6$ と $15$ を1つの表とする時には、 $2,3,5$ が素数リストとなります。

で、指数を並べると以下の通り。

各素数ごとの指数の最大値、最小値を計算。

$6$ と $15$ の場合だと、指数は $0$ か $1$ しかないですが。

素数	6を展開	15を展開	指数の最大値	指数の最小値
2	1	0	1	0
3	1	1	1	1
5	0	1	1	0

なので、以下の通り求められます。

$2^{1} \times 3^{1} \times 5^{1} = 60$

$2^{0} \times 3^{1} \times 5^{0} = 3$

次回、実装編。

*1:正の整数 $a,b$ に対して，それらの最大公約数を $g$ ，最小公倍数を $l$ とおくと $a \times b = g \times l$