ある整数xとyの最大公約数を出す時の法則を見つけた

前回のエントリで最小公倍数を出す法則を見つけたが、その過程で最大公約数を出している事が分かった。

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とyの最小公倍数を出す時の法則を見つけた – NAL-6295の舌先三寸

上記例を使うと、

xの素因数 2,2,3とyの素因数 2,2,5のうちの重複部分である、

2,2

をかけると、4となり、

12と20の最大公約数は4である。

となる。

Share