ユークリッド互除法の意義

質問

２つの数の最大公約数の求め方の１つとしてユークリッド互除法を学習しました。
しかし、最大公約数の求め方は素因数分解でも求められます。
共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは？と思うのですが、ユークリッド互除法を使うことのよさってあるのですか？

回答よろしくお願いいたします。

回答No.1

f272 · ベストアンサー

素因数分解をするときに，割る数はどう決めるのですか？2,3,5,7,9,...と順に試すのですか？与えられた数が簡単な数ならばそれでもいいけど，効率が悪すぎです。
例えば879017と902801の最大公約数は何？

回答No.3

Tacosan

そう, 「素因数分解できる」なら, ユークリッドの互除法はいらない. そして, 小さい数であれば実際に素因数分解した方が速い.

ただ, 相手が大きくなると話が変わってくる. つまり, 「効率的に素因数分解する方法」は知られていないのに対してユークリッドの互除法は非常に効率的に実行できる. その結果,
1000桁の数の素因数分解を実行する
よりも
100000桁の 2つの数に対してユークリッドの互除法を実行する
方がはるかに簡単だったりする.

回答No.2

hashioogi

プログラマです。

プログラミングの世界では時たま結構桁数の大きい数の数の最大公約数を求める必要が出てきます。CPUは早いのでほとんどの場合人間の感覚では、ユークリッド互除法でも共通に割れる数を探す方法でもあまり差はないように感じる場合が多いですが、ユークリッド互除法の方が圧倒的に高速なのは間違いありません。