素因数分解で最大公約数、最小公倍数を求める方法

質問

例えば

　24と18を使って素因数分解すると

2 |24　18
3 |12　 9
　　　4　3

となって共通の素因数をかけて6が最大公約数
共通の素因数と、共通の素因数を抜いた数を掛けて　72が最小公倍数

というふうに求めますが

これは素数である必要はあるのですか?

別に

6|　24　18
　　　4　　3

として求めても同じではないのですか?
下の方法で何か困ることはあるのでしょうか？

回答No.6

bgm38489 · ベストアンサー

＞＞素因数分解で最大公約数、最小公倍数を求める方法
素因数分解というと、７２＝２＊２＊２＊３＊３と素数に分解することですから、素因数分解で求めなさい、となると素数で割っていくしかありませんがね。指定されていなければ、公約数分解（？）で求めてもいいわけです。

例えば、２８８と６４８について求めるとなると、いちいち素数で割っていくわけにはいかない。１８と２４のように、いきなり最大公約数で割ることもできない（慣れてくればできますが）。
８｜２８８　６４８
９｜　３６　　８１　
　　　　４　　　９
最大公約数は８＊９＝７２、最小公倍数は８＊９＊４＊９＝２５９２ですね。

お礼

みなさんありがとうございます。

回答No.7

中村 拓男（@tknakamuri）

素因数分解でもいいことはありますよ。

24 = 2^3 x 3^1
90 = 2^1 x 3^2 x 5^1

最大公約数は次数の小さい方の素因数を掛け合わせればよいので

2^1 x 3^1 = 6

最小公倍数は次数の大きい方の素因数を掛け合わせればよいので

2^3 x 3^2 x 5^1 = 360

共通の因数とかは考えず、個別に分解すればよいし、
分解さえ済めば後は機械的に作業できます。対象の数が
たくさんあっても作業は簡単です。

数がたくさんあるなら私なら迷わずこのやり方でやります。

回答No.5

alice_44

とりあえず、問題は何も無いです。

拡張として、それと似たような方法で
３個以上の数の「最小公倍数」を求める場合には、
素数以外を約数に立てると、
ちょっとマズいことが起りますが。

回答No.4

178-tall

>6|　24　18
>　　　4　　3
>として求めても同じではないのですか?

結果は同じ。

>下の方法で何か困ることはあるのでしょうか？

一発で最大公約数をみつけるのにこだわると、かえって骨が折れる。
小さな公約数から始めるのが無難。

回答No.3

noname#190065

あなたの問い「素因数分解で」と書いてありますから、素数で分解する必要があります。
単に、最大公約数、最小公倍数を求めるなら、正しい答えであればどのように求めてもいいのです。

回答No.2

Cupper-2

問題は無い。

ただし、それは「６」が解っているときにだけ使える方法です。
でしょ？
６が解らないときは２と３で商を求め、それらが因数かを確認するはずです。

ですので正しい計算過程としては、素数で因数分解をするわけです。

回答No.1

noname#207523

素数である必要はありません。

ただ、素因数分解をした方が時間はかかるかもしれませんが、
初歩的なミスを見つけられることが多くなります。