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

例えば

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


2 |24　18
3 |12　 9
　　　4　3

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

というふうに求めますが

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

別に

6|　24　18
　　　4　　3

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

No.6 ベストアンサー 回答者： bgm38489 回答日時： 2013/10/22 18:49

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

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

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

この回答へのお礼

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

お礼日時：2013/10/22 19:51

No.7 回答者： tknakamuri 回答日時： 2013/10/22 19:18

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

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 回答日時： 2013/10/22 18:46

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

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

No.4 回答者： 178-tall 回答日時： 2013/10/22 18:46

>6|　24　18

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

結果は同じ。


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

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

　　

No.3 回答者： sirayaki 回答日時： 2013/10/22 18:44

　あなたの問い「素因数分解で」と書いてありますから、素数で分解する必要があります。

単に、最大公約数、最小公倍数を求めるなら、正しい答えであればどのように求めてもいいのです。

No.2 回答者： Cupper-2 回答日時： 2013/10/22 18:37

問題は無い。

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

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

No.1 回答者： mattsu0730 回答日時： 2013/10/22 18:30

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

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