最大公約数の求め方

質問

「２つの整数1271と1517の最大公約数を求めなさい」
という問題があります。

答えは「41」なのですが、

素数を順番に試していくしか方法しかないのでしょうか？

回答No.3

178-tall · ベストアンサー

#2 さんのおっしゃる「互除法」とは、参考 URL にあるユークリッドの互除法。

参考URL：

http://www.cwo.zaq.ne.jp/bfaby300/math/gojyo.html

お礼

参考URLまでいただき、ありがとうございました。

回答No.2

hashioogi

互除法は調べましたか ?

お礼

「互除法」というものは知りませんでした。
ありがとうございました。

回答No.1

osaka-girl

えー最大公約数だから、素因数分解すればいいのですよね。
素因数分解のことを素数を順番に試すというのであれば、
その通りだと思います。

お礼

早速の回答ありがとうございました。