ユークリッドの互除法

 プログラムでは、検索とか並べ替えとかよく出てくる問題があって、それらはに定番のアルゴリズムがあります。ですから、プログラマーはすべてのアルゴリズムを自分で考えるわけではありません。既に知られているアルゴリズムはどんどん使って、さらに複雑な作業を実現するのです。つまりアルゴリズムは人類が共有する知的財産なのです。
 ユークリッドの互除法は、2つの自然数 a、b の最大公約数を求める方法です。最大公約数を求めるには2数をそれぞれ素因数分解して共通の素因数を見つけると中学校で教えられます。でも、素因数分解って面倒ですよね。結構カンが必要だったりしますから。
 ユークリッドの方法は a、b(aの方が大)に関して、a を b で割った剰余(余り)を r とすると、a と b の最大公約数は b と r の最大公約数になるという性質を使います。つまり a÷b の剰余を r1、b÷r1の剰余を÷r2、r1÷r2の剰余をr3というように繰り返し、剰余が0になったら除数が最大公約数になります。例えば、195 と 143 で考えてみましょう。

 ・195 ÷ 143 = 1 … 52
 ・143 ÷ 52 = 2 … 39
 ・ 52 ÷ 39 = 1 … 13
 ・ 39 ÷ 13 = 3 … 0
ですから最大公約数は13です。
 ユークリッドという人は、ユークリッド幾何学のあのユークリッド、で紀元前4世紀頃のギリシャの数学者です。ちゃんとした記録に残るアルゴリズムとしては最も古いものだそうです。しかしこれが有名なのは古いというより「意外な方法」という点に魅力があるからではないでしょうか。 --- Y.O. ---



→ IT用語 もくじ       → TOP へ