前回のエントリで最小公倍数を出す法則を見つけたが、その過程で最大公約数を出している事が分かった。
xとyの素因数リストの中にある重複部分を掛けた結果が最大公約数。
重複した部分が無い場合は1が最大公約数。
xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、
xの素因数リストとyの素因数リストの重複部分を打ち消し、
残ったxの素因数リストを乗算して算出した値にyを掛けると、
xとyの最小公倍数になる。
例:
xが12でyが20の時、
xの素因数が2,2,3
yの素因数が2,2,5
重複部分を打ち消しあうと
xの素因数の残りが3
yの素因数の残りが5
yにxの素因数の残りを掛けると60
(ついでに)xにyの素因数の残りを掛けても60
上記例を使うと、
xの素因数 2,2,3とyの素因数 2,2,5のうちの重複部分である、
2,2
をかけると、4となり、
12と20の最大公約数は4である。
となる。
