目次（まとめ）
◾️ ユークリッド互除法は、最大公約数を見つけるための最古のアルゴリズム
◾️ Rubyをつかったユークリッド互除法
こんにちは、みっちゃんです。
今回の記事では、2つの自然数について、最大公約数を発見するためのアルゴリズムである「ユークリッド互除法」を紹介します。
ユークリッド互除法は、最大公約数を見つけるための最古のアルゴリズム
みなさんは「最大公約数」と聞いて、何か覚えていますか？
例えば、"12" と "26" の最大公約数は、以下のように考えてきたと思います。
12 : 1, 2, 3, 4, 6, 12
26 : 1, 2, 13, 26
となるので、最大公約数は "2" になる。このように、比較的小さい2つの自然数について、最大公約数を求めることは比較的簡単ですが、例えば、"1346" と "5439" の最大公約数は？と言われたときに、上のように計算するのは大変な作業になります。
そこで「ユークリッド互除法」と呼ばれるアルゴリズムが提案されました。
このアルゴリズムでは、名前で示されているように「互いに割り算（除法）をする」ということになります。
26 ÷ 12 = 2 あまり 2
12 ÷ 2 = 6 あまり 0
となるので、最大公約数は "2" になる。5439 ÷ 1346 = 4 あまり 55
1346 ÷ 55 = 24 あまり 26
55 ÷ 26 = 2 あまり 3
26 ÷ 3 = 8 あまり 2
3 ÷ 2 = 1 あまり 1
2 ÷ 1 = 2
となるので、最大公約数は "1" になるこのように、割り算における「割られる値（分数でいう分子）」と「割る値（分数でいう分母）」を考えるとき、「割る値」を「あまり」で割り続けて、最大公約数を見つけます。
Wikipediaによると、この「ユークリッド互除法」は、最古のアルゴリズムとして知られています。
Rubyをつかったユークリッド互除法
ユークリッド互除法は、上で示したように、同じ処理を繰り返す手法は、再帰のアプローチを使ってプログラミングすることが可能です。
以下は、Rubyを使ったプログラム例です。
1: def euclidean(a, b)
2: if b == 0
3: return a
4: else
5: euclidean(b, a % b)
6: end
7: end
8:
9: p euclidean(5439, 1346)9行目において、最大公約数を求めたい2つの自然数 "5439" と "1346" を "euclidean" という関数の引数に与えています。
"euclidean" という関数は、1行目から7行目にかけて定義しています。
この定義の中で、"euclidean" という関数を呼び出しているということで、「b = 0」という条件を満たすまで、繰り返し計算が行われるような仕組みになっています。
