ユークリッドの互除法
ユークリッド(Euclid)の互除法は、２つの整数の最大公約数を求めるアルゴリズムです。
「プログラムで最大公約数を求めてどうするんだ」なんて思う方がいるかもしれませんが
私は、１度だけこのアルゴリズムをプログラム内で使用したことがあります。
まぁ、知っておいて損はしないでしょう。
ユークリッドの互除法
(1) 正の整数 m,n を指定して(2)へ
(2) m,nの大小比較を行う
(3) m = nなら m が m,nの最大公約数である(終了)。違う場合は(4)へ
(4) 大きいほうから小さいほうを引き、m とする。小さいほうを n として(2)へ
サンプルプログラムは、そのうち…