ユークリッドの互除法@20060416235303

最大公約数を求めるときに使うアルゴリズムとして有名。
原理は,15と21 の最大公約数を求めるときに,

>|
  21 - 15 = 6  ← 3*7 - 3*5 = 3*2 で,引き算して出てきた数も最大公約数が残っている。
  15 -  6 = 9 
   9 -  6 = 3 
   6 -  3 = 3 ← 3 と 3 と同じ数字が出たのでここで終了
|<

少々複雑ではあるが、Nader H. Bshoutyのアルゴリズムの方が高速である。

 *リスト:[[リスト::数学関連]]