ユークリッドの互除法(最大公約数を求めるアルゴリズム)｜Excel VBAで学ぶ数学とアルゴリズム
今回は任意の自然数の最大公約数を求める「ユークリッドの互除法」について解説していきます。
アルゴリズムとしての歴史は非常に深く、明示的に記述された最古のアルゴリズムといわれていてその誕生は紀元前3世紀にまで遡るアルゴリズムです。
アルゴリズムとしては非常に簡単で四則演算(和差積商)がわかっていればすぐに理解できる内容です。
本ページではこの「ユークリッドの互除法」のアルゴリズムがどういった仕組みなのかを解説し、最終的にExcel VBAのコードとして実装していきます。
ユークリッドの互除法
ユークリッドの互除法のアルゴリズムは非常にシンプルで下記の通りです。
① 上記式の \(x\) に自然数 \(a\) を、\(y\) に自然数 \(b\) をそれぞれ代入して、余り \(r\) を求める
② 上記式の \(x\) に自然数 \(b\) を、\(y\) に①で求めた \(r\) をそれぞれ代入して、余り \(r\) を求める
③ 上記式の \(x\) に①で求めた \(r\) を、\(y\) に②で求めた \(r\) をそれぞれ代入して、余り \(r\) を求める
④ 上記の要領で余り \(r\) が「0」になるまで除算し続ける
⑤ 余り \(r\) が「0」になったときの \(y\) の値が自然数 \(a,b\) の最大公約数
２つの自然数 \(a,b\) (\(a>b\)) において、\(a ÷ b\) の余りを \(r\) とすると、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数と等しいという性質があります。この性質から「割る数(\(y\))」と「余り(\(r\))」の除算を再帰的に続けると「余り(\(r\))」が０になった時の「割る数(\(y\))」が自然数 \(a,b\) の最大公約数となります。
文字だけだとわかりづらいので具体例で見てみましょう。
たとえば「252」「105」という自然数の最大公約数を調べる場合は下記のような計算を行います。
「252」と「105」の最大公約数を求める
・252 ÷ 105 = 2 … 42
・105 ÷ 42 = 2 … 21
・ 42 ÷ 21 = 2 (… 0)
余りが「0」になったため「21」が最大公約数
これまでの説明を読んでいなくても上記の計算を見たらアルゴリズムは理解できると思います。
最大公約数は英語で「Greatest Common Divisor」といい、その頭文字をとって、\(a\) と \(b\) の最大公約数のことを \(gcd(a,b)\) のように表記されることがあります。本ページではこういった表記はしていませんが「gcd」という文字が出てきたら「最大公約数のことを意味しているんだな」と思ってもらえれば大丈夫です。
ちなみにアルゴリズム名にもある「ユークリッド」ですが、これは古代ギリシア(紀元前3世紀)の数学者の名前です。このユークリッドが書いたとされる『ユークリッド原論』にこのアルゴリズムが記されていたことから「ユークリッドの互除法」と呼ばれるようになりました。
サンプルコード
ユークリッドの互除法をVBAで書くと下記の通りです。
EuclideanAlgorithm関数は引数として入力された2個の数の最大公約数を返します。
Sub main()
'ユークリッドの互除法
Debug.Print EuclideanAlgorithm(252, 105)
End Sub
'------------------------------------------------------------------
' ユークリッドの互除法
' iNum1 ：入力値①
' iNum2 ：入力値②
' 戻り値 ：最大公約数
'------------------------------------------------------------------
Function EuclideanAlgorithm(iNum1 As Long, iNum2 As Long) As Long
Dim a As Long
Dim b As Long
Dim r As Long
'数値の大きい方の入力値を[a],小さい方の入力値を[b]に代入
If (iNum1 > iNum2) Then
a = iNum1
b = iNum2
Else
a = iNum2
b = iNum1
End If
'余りが0になるまで除算を繰り返す
r = a Mod b
Do While r <> 0
a = b
b = r
r = a Mod b
Loop
'最大公約数を返す
EuclideanAlgorithm = b
End Function
3個以上の自然数の最大公約数を求める
上記までの内容で求めることができるのは自然数が2個の場合の最大公約数です。
自然数が3個以上ある場合のユークリッドの互除法のアルゴリズムは下記の通りです。
② 前で求めた最大公約数と3個目の自然数の最大公約数を求める
③ 前で求めた最大公約数と4個目の自然数の最大公約数を求める
：
④ 前で求めた最大公約数とN個目の自然数の最大公約数を求める
上記の通りで自然数が3個以上になったとしてもやることは基本的には同じです。
「「1個目の数と2個目の数の最大公約数」と3個目の数の最大公約数」と4個目の数との最大公約数」のようにネスト(入れ子)のようになっているとイメージすればわかりやすいと思います。
ではこちらの場合も、先ほどと同じく具体例でみてみましょう。
「252」「105」「129」という3個の自然数の最大公約数を調べる場合は下記のようになります。
「252」と「105」と「129」の最大公約数を求める
(1)「252」と「105」の最大公約数を求める
・252 ÷ 105 = 2 … 42
・105 ÷ 42 = 2 … 21
・ 42 ÷ 21 = 2 (… 0)
「252」と「105」の最大公約数は「21」が最大公約数
(2)「129」と「21」の最大公約数を求める
・129 ÷ 21 = 6 … 3
・21 ÷ 3 = 7 (… 0)
「252」と「105」と「129」の最大公約数は「3」が最大公約数
3個以上の自然数の最大公約数を求めるには上記のように、自然数2個のときにやった計算を繰り返し行うだけで簡単に求めることができます。
サンプルコード
3個以上の数に対応させたユークリッドの互除法をVBAで書くと下記の通りです。
EuclideanAlgorithmMulti関数は引数として入力された3個以上の数の最大公約数を返します。
引数として入力するのは配列のため「Array(〇,〇,〇)」の中身が入力値となります。
入力要素数に制限はないので入力する要素が4個、5個と増えても実行可能です。
Sub main()
Dim N() As Long
Dim vN() As Variant
Dim i As Long
'入力値設定
vN = Array(252, 105, 129)
'VarinantをLong型に変換
ReDim N(UBound(vN))
For i = 0 To UBound(vN)
N(i) = vN(i)
Next i
'ユークリッド互除法(複数入力対応)
Debug.Print EuclideanAlgorithmMulti(N)
End Sub
'------------------------------------------------------------------
' ユークリッドの互除法(複数入力対応)
' N() ：入力値
' 戻り値 ：最大公約数
'------------------------------------------------------------------
Function EuclideanAlgorithmMulti(N() As Long) As Long
Dim gcd As Long
Dim i As Long
'1個目と2個目の自然数の最大公約数を求める
gcd = EuclideanAlgorithm(N(0), N(1))
'3個目以降は1つ前に求めた求めた最大公約数を利用する
For i = 2 To UBound(N)
gcd = EuclideanAlgorithm(gcd, N(i))
Next i
EuclideanAlgorithmMulti = gcd
End Function
'------------------------------------------------------------------
' ユークリッドの互除法
' iNum1 ：入力値①
' iNum2 ：入力値②
' 戻り値 ：最大公約数
'------------------------------------------------------------------
Function EuclideanAlgorithm(iNum1 As Long, iNum2 As Long) As Long
Dim a As Long
Dim b As Long
Dim r As Long
'数値の大きい方の入力値を[a],小さい方の入力値を[b]に代入
If (iNum1 > iNum2) Then
a = iNum1
b = iNum2
Else
a = iNum2
b = iNum1
End If
'余りが0になるまで除算を繰り返す
r = a Mod b
Do While r <> 0
a = b
b = r
r = a Mod b
Loop
'最大公約数を返す
EuclideanAlgorithm = b
End Function
まとめ
今回は任意の自然数の最大公約数を求めるの「ユークリッドの互除法」の解説でした。
$$ x ÷ y = z \cdots r \quad (x > y)$$
① 上記式の \(x\) に自然数 \(a\) を、\(y\) に自然数 \(b\) をそれぞれ代入して、余り \(r\) を求める
② 上記式の \(x\) に自然数 \(b\) を、\(y\) に①で求めた \(r\) をそれぞれ代入して、余り \(r\) を求める
③ 上記式の \(x\) に①で求めた \(r\) を、\(y\) に②で求めた \(r\) をそれぞれ代入して、余り \(r\) を求める
④ 上記の要領で余り \(r\) が「0」になるまで除算し続ける
⑤ 余り \(r\) が「0」になったときの \(y\) の値が自然数 \(a,b\) の最大公約数
このユークリッドの互除法を利用するアルゴリズムとして、素数判定アルゴリズム「フェルマーテスト」というものがあります。ユークリッドの互除法よりは難しい内容ですが、高校数学がある程度理解できるのであれば十分に理解できる内容なので、是非合わせて勉強してみて下さい。
