【Python】最大公約数を求めるアルゴリズム2選！プログラムで自動化！

こんにちは、Youta(@youta_blog)です。

今回は、最大公約数を求めるお話です。

すずか

部屋の模様替えで、床一面にタイル敷くよー。

でもだるいから、極力最低限の枚数だけにしたいなー。

先生

素敵ですね。

最大公約数を利用すると、必要なタイルの枚数がわかりますよ。

すずかさんの部屋の間取りを元に、こんな問題を作ってみました。

問題

縦\(300\ cm\)、横\(420\ cm\)の床を、可能な限り大きな正方形のタイルで敷き詰める。

\((1)\)　タイルの一辺の長さは何\(cm\)か。

\((2)\)　タイルの枚数を求めよ。

実はこの問題、最大公約数が深く関わっています。

本記事を読めば、この問題の対処法を学べます。

また、最大公約数を求める有名なアルゴリズム・証明を解説します。

さらには、コンピュータで自動で最大公約数を求めるプログラムもご紹介します。

最大公約数の利用

まず始めに、冒頭の問題の答えを示します。

答え

\((1)\)　\(60\ cm\)

\((2)\)　\(35\)枚

すずか

どうやって求めたん？

最大公約数が必要な理由

実は\((1)\)の答え\(60\)は、縦の長さ\(300\)と横の長さ\(420\)の最大公約数です。

すずか

なぜに最大公約数？

例えば、タイル張りが苦でない人は一辺\(10\ cm\)のタイルを床に敷こうとするでしょう。

縦に\(30\)個、横に\(42\)個のタイルを敷けばピッタリです。

しかし、タイルの予算や労力を考えると現実的ではないですよね。

すずか

じゃあ一辺\(100\ cm\)とかでやれば良いじゃん。

先生

言いましたね？やりますよ？

はい、タイルの枚数が\(12\)枚ですので作業が楽になりました。

ですが、余った部分が発生しました。

どうやら、適当なサイズではタイルを床にピッタリと敷き詰められないことがわかります。

そこで、隙間なく敷き詰めるために約数を考えなければならないのです。

すずか

いや流石に約数は知ってるけど、なんで？

仮に床をタイルで隙間なく敷き詰められたときを考えましょう。

下図は、先ほどの一辺\(10\ cm\)のタイルの例です。

縦に\(30\)個、横に\(42\)個のタイルが敷かれているのでしたね。

このとき、縦の長さ\(=\)タイルの一辺\(×\)縦に並ぶタイルの枚数です。

\(300 = 10 × 30\)ですからね。

同様に、横の長さ\(=\)タイルの一辺\(×\)横に並ぶタイルの枚数です。

\(420 = 10 × 42\)ですから。

つまり、床をタイルで完全に敷き詰めたとき、タイルの一辺は縦横の長さの公約数です。

一辺\(100\ cm\)のタイルで失敗するのは、\(100\)が\(300\)と\(420\)の公約数ではないからです。

実際に\(420=100×4+20\)ですから、横に\(20\ cm\)の余りが生じます。

\(2\)数の公約数を見つけることは、
その\(2\)数を辺とする長方形に、ピッタリ敷き詰められる正方形の一辺を探すのと同じです。

したがって、タイルの一辺の候補は、\(300\)と\(420\)の公約数です。

そして一番大きなタイルの一辺とは、公約数の最大値、つまり最大公約数ですね。

次章では、\(300\)と\(420\)の最大公約数を求める方法を解説します。

\(2\)数の最大公約数の視覚的理解

\(300\)と\(420\)の最大公約数を求めます。

素因数分解を使っても良いですが、ここでは図形的に最大公約数を求めてみましょう。

結論、取り敢えず面積が許す限りの巨大なタイルを順に敷き詰めていきます。

「もうタイルを敷けない！」となるときのタイルの一辺が、\(300\)と\(420\)の最大公約数です。

まず、一辺\(300\ cm\)のタイルを床に敷きます。

さらに、余った領域に一辺\(120\ cm\)のタイルを敷きます。

一辺\(60\ cm\)のタイルを\(2\)枚敷き、とうとう床が見えなくなりました。

すずか

だからなんなの？

先生

面白いのはこれからです。

今度は逆に、小さな視点から大きな視点に変えていきますよ。

\(60\)と\(120\)の最大公約数は\(60\)です。

ゆえに、一辺\(60\ cm\)の緑のタイルで一辺\(120\ cm\)の黄色のタイルを隙間なく埋められます。

また、\(120\)と\(300\)の最大公約数も\(60\)です。

よって、一辺\(60\ cm\)の緑のタイルで一辺\(300\ cm\)の赤のタイルも隙間なく埋められます。

床が一辺\(60\ cm\)の緑のタイルでピッタリ埋まるので、\(60\)は\(300\)と\(420\)の公約数です。

また、できる限り大きなタイルから順に敷いていったので、
一辺\(60\ cm\)の緑のタイルもできる限り大きいはずです。

したがって、\(60\)が\(300\)と\(420\)の最大公約数となり、求める数値となるのです。

最後に、タイルの枚数を求めて問題を締め括りましょう。

縦には\(300÷60\)で\(5\)枚並んでおり、横には\(420÷60\)で\(7\)枚並んでいます。

したがって、\(5×7\)でタイルの枚数は\(35\)枚です。

答え

\((1)\)　\(60\ cm\)

\((2)\)　\(35\)枚

ユークリッドの互除法

先ほどは、視覚的に最大公約数を求めました。

ですが、実際やった手順はユークリッドの互除法そのものです。

ユークリッドの互除法とは、2つの整数の最大公約数を求めるアルゴリズムです。

次のプロセスにより、最大公約数が求まります。

これは、古代ギリシアの数学者ユークリッドの発見による最大公約数を求める手法です。

先生

具体例で説明しましょう。

具体例

\(a = 420\)と\(b = 420\)の最大公約数をユークリッドの互除法で求めます。

上図の\(3\)本の計算式を順に解説します。

420と300の最大公約数

②より、\(a = 420\)を\(b = 300\)で割った余り\(r = 120\)を求めます。

\(300H×420W\)の長方形に一辺\(300\)のタイルを\(1\)つ敷くと、横に\(120\)余る状態です。

現時点で\(a = 420\)と\(b = 300\)と\(r = 120\)ですね。

しかし、③より新たに\(a = b\)、\(b = r\)とします。

そして、次は\(a = 300\)と\(b = 120\)の最大公約数を求めるのです。

300と120の最大公約数

②より、\(a = 300\)を\(b = 120\)で割った余り\(r = 60\)を求めます。

\(300H×120W\)の長方形に一辺\(120\)のタイルを\(2\)つ敷くと、縦に\(60\)余る状態です。

現時点で\(a = 300\)と\(b = 120\)と\(r = 60\)ですね。

しかし、③より新たに\(a = b\)、\(b = r\)とします。

そして、次は\(a = 120\)と\(b = 60\)の最大公約数を求めるのです。

120と60の最大公約数

②より、\(a = 120\)を\(b = 60\)で割った余り\(r = 0\)を求めます。

\(60H×120W\)の長方形に一辺\(60\)のタイルを\(2\)つ敷くと、余りが生じない状態です。

現時点で\(a = 120\)と\(b = 60\)と\(r = 0\)ですね。

しかし、③より新たに\(a = b\)、\(b = r\)とします。

そして、次は\(a = 60\)と\(b = 0\)の最大公約数を求めるのです。

と言いたいところですが、①より\(b = 0\)のときは\(a = 60\)を最大公約数とするのでした。

つまり、この\(60\)こそが元の\(420\)と\(300\)の最大公約数です。

ユークリッドの互除法の強みは、最大公約数を求めたい\(2\)数を徐々に小さくすることです。

今回は\(420\)と\(300\)の最大公約数 = \(300\)と\(120\)の最大公約数 = \(120\)と\(60\)の最大公約数 でした。

\(420\)と\(300\)の最大公約数を求める代わりに、\(120\)と\(60\)の最大公約数を求めれば良いのです。

よって、どんなに巨大な数同士でも、必ず有限回の操作で最大公約数を求められます。

とはいえ、多くの方が疑問に思ったはずです。

なぜ、割られる数と割る数の最大公約数 = 割る数と余りの最大公約数なのか。

次はこの理由について解説します。

証明

ユークリッドの互除法は、以下の数学的事実に立脚します。

自然数\(a\)と\(b\)について、\(a\)を\(b\)で割ったときの余りを\(r\)とする。
このとき、\(a\)と\(b\)の最大公約数は、\(b\)と\(r\)の最大公約数に等しい。

以降、\(a\)と\(b\)の最大公約数を\(\gcd{(a, b)}\)と表記することにします。

先生

\(\gcd{}\)とは、最大公約数の英訳・greatest common divisorの略です。

プログラム

実装例

ユークリッドの互除法を用いて、最大公約数を求めるPythonプログラムの例です。

def euclidean_gcd(a, b):
    a, b = abs(a), abs(b)

    while b:
        a, b = b, a % b
    return a

ユークリッドの互除法のアルゴリズムをeuclidean_gcd 関数で実装しました。

\(2\)つの整数を入力し、それらの最大公約数を計算します。

実行例です。

num1 = 527
num2 = 341

result = euclidean_gcd(num1, num2)
print(result)
# 31

解説

whileループは、bがTrue(\(\ne 0\))である限り、繰り返し処理を行います。

言い換えると、bが\(0\)になるとループを抜けます。

    while b:

ユークリッドの互除法は b が\(0\)になったときに終わりますよね。

ここでは、変数の入れ替えを行なっています。

    a, b = b, a % b

a は今のb の値に置き換えられます。

また、bは aを bで割った余り(a % b)に置換されます。

Binary GCD Algorithm (Stein’s Algorithm)

この章だけはハイレベルなので、本職のエンジニアの方向けになります。
興味がある方は、雰囲気だけでも一緒に楽しみましょう！

先ほどは、ユークリッドの互除法を紹介しました。

実は、もう一つ有名な最大公約数を求めるアルゴリズムが存在します。

それが、Binary GCD Algorithm(以下「バイナリ・ユークリッドの互除法」)です。

ユークリッドの互除法とほぼ同時期に中国で発見されたと言われるアルゴリズムです。

\(1967\)年にイスラエルの学者・ジョセフ=シュタインさんに再発見されました。

コンピューターが得意な\(2\)の除算を数多く取り入れ、高速化を試みている点が特徴です。

具体例

\(a = 18\)と\(b = 12\)の最大公約数をバイナリ・ユークリッドの互除法で求めます。

上図の\(5\)本の計算式を順に解説します。

18と12の最大公約数

\(a = 18\)と\(b = 12\)では、\(a\)も\(b\)も偶数です。

②より
\(\gcd{(a, b)}=2\gcd{(\frac{a}{2}, \frac{b}{2})}=2\gcd{(\frac{18}{2}, \frac{12}{2})}=2\gcd{(9, 6)}\)

このとき、共通因数として\(2\)を保存しておきます。・・・★

先に\(\gcd{(9,6)}\)を求めて、最後に\(2\)を掛け合わせる流れです。

ここまでは\(a = 18\)、\(b = 12\)でしたが、新たに\(a = 9\)、\(b = 6\)として次に進みます。

9と6の最大公約数

\(a = 9\)と\(b = 6\)では、\(a\)が奇数で\(b\)が偶数です。

③より
\(\gcd{(a, b)}=\gcd{(a, \frac{b}{2})}=\gcd{(9, \frac{6}{2})}=\gcd{(9, 3)}\)

ここまでは\(a = 9\)、\(b = 6\)でしたが、新たに\(a = 9\)、\(b = 3\)として次に進みます。

9と3の最大公約数

\(a = 9\)と\(b = 3\)では、\(a\)も\(b\)も奇数です。

④より
\(\gcd{(a, b)}=\gcd{(\frac{|a-b|}{2}, \min{(a, b)}})=\gcd{(\frac{|9-3|}{2}, \min{(9, 3)}})=\gcd{(3, 3)}\)

ここまでは\(a = 9\)、\(b = 3\)でしたが、新たに\(a = 3\)、\(b = 3\)として次に進みます。

3と3の最大公約数

\(a = 3\)と\(b = 3\)では、\(a\)も\(b\)も奇数です。

④より
\(\gcd{(a, b)}=\gcd{(\frac{|a-b|}{2}, \min{(a, b)}})=\gcd{(\frac{|3-3|}{2}, \min{(3, 3)}})=\gcd{(0, 3)}\)

現時点で\(a = 3\)、\(b = 3\)ですが、新たに\(a = 0\)、\(b = 3\)とします。

3と0の最大公約数

\(a = 0\)と\(b = 3\)では、・・・としたいところですが、\(a=0\)となりましたね。

①より\(\gcd{(0, 3)}=3\)です。

また、★で保存しておいた共通因数の\(2\)を今の\(3\)に掛け合わせます。

\(2×3\)より、\(6\)が元の\(18\)と\(12\)の最大公約数です。

計算の流れはご理解いただけたと思います。

ですが、やはり理屈がわからないと落ち着かないですよね。

ということで、次はバイナリ・ユークリッドの互除法の数学的な解説をします。

証明

\(a\)と\(b\)は自然数として、次の\(4\)つを証明・解説します。

\((1)\)　\(\gcd{(a, 0)} = a\)
\((2)\)　\(a\)も\(b\)も偶数\(\Rightarrow\)\(\gcd{(a, b)} = 2\gcd{(\frac{a}{2}, \frac{b}{2})}\)
\((3)\)　\(a\)のみが偶数\(\Rightarrow\)\(\gcd{(a, b)} = \gcd{(\frac{a}{2}, b)}\)
\((4)\)　\(a\)も\(b\)も奇数\(\Rightarrow\)\(\gcd{(a, b)} = \gcd{(\frac{|a-b|}{2}, \min{(a, b)})}\)

\(a\)と\(0\)の最大公約数は\(a\)

\(\gcd{(a, 0)} = a\)の説明をします。

まずは、\(0\)の約数について考えましょう。

そもそもある整数\(n\)の約数とは、\(n\)を割り切れる整数のことでした。

例えば、\(6\)は\(36\)を割り切れるので、\(36\)の約数です。

では、\(6\)は\(0\)を割り切れるでしょうか？

\(0÷6=0\)であり、余りはないので割り切れています。

したがって、\(6\)は\(0\)の約数です。

すずか

あれ、これ別に\(6\)に限った話じゃなくない？

先生

良い着眼点ですね。

\(0÷11=0\)や\(0÷100=0\)から\(11\)も\(100\)も\(0\)の約数だとわかります。

つまり、すべての整数は\(0\)の約数なので、当然整数\(a\)も\(0\)の約数です。

また、\(a\)は\(a\)自身を最大公約数として持つので、\(\gcd{(a, 0)} = a\)が導かれます。

実は、この論理では\(\gcd{(0, 0)}\)を上手く説明できません。
しかし、その議論をこの場で行うことは、本筋から逸れるため割愛します。
ご興味のある方は、下記記事が大変参考になるので良かったらどうぞ。
https://qiita.com/reika727/items/9c317bf562b5df966cbf

共に偶数ならば、両方\(2\)で割り最後に\(2\)倍

\(a\)も\(b\)も偶数\(\Rightarrow\)\(\gcd{(a, b)} = 2\gcd{(\frac{a}{2}, \frac{b}{2})}\)の説明をします。

以下、\(a\)と\(b\)は共に偶数より、\(\frac{a}{2}\)と\(\frac{b}{2}\)は整数であることに注意してください。

一方が偶数ならば、それだけを\(2\)で割る

\(a\)のみが偶数\(\Rightarrow\)\(\gcd{(a, b)} = \gcd{(\frac{a}{2}, b)}\)の説明をします。

証明しても良いですが、具体例でサクッといきましょう。

例えば、\(54\)と\(45\)の最大公約数を求めましょう。

このとき、\(54\)と\(45\)は\(2\)を公約数に持つ可能性があると思いますか？

いいえ、奇数の\(45\)は\(2\)で割り切れるわけがありません。

\(54 = 2・27\)なので、結局\(27\)の約数と\(45\)の約数を調べていけば十分ですよね。

よって、\(27\)と\(45\)の最大公約数が、元の\(54\)と\(45\)の最大公約数になるのです。

つまり、\(a\)のみが偶数のとき\(\gcd{(a, b)} = \gcd{(\frac{a}{2}, b)}\)です。

共に奇数ならば、差を\(2\)で割り小さい方を選ぶ

\(a\)も\(b\)も奇数\(\Rightarrow\)\(\gcd{(a, b)} = \gcd{(\frac{|a-b|}{2}, \min{(a, b)})}\)の説明をします。

まずは、自然数\(a\)と\(b\)を\(a \ge b\)として\(\gcd{(a, b)} = \gcd{(a – b, a)}\)を証明します。

証明自体はユークリッドの互除法と同様の流れです。

ですが、せっかくなので背理法を使った手法でいきます。

すずか

え なんで\(\gcd{(a – b, a)}\)だけ？\(\gcd{(a – b, b)}\)じゃダメ？

当然、\(\gcd{(a, b)} = \gcd{(a – b, b)}\)も成り立ちます。

したがって、\(a\)と\(b\)のどちらか小さい方を選べば、計算が効率的ですね。

そこで、\(a\)と\(b\)の小さい方を\(\min{(a, b)}\)として\(\gcd{(a, b)} = \gcd{(a – b, \min{(a, b)})}\)とします。

また、先ほどの証明では\(a – b\)が負の数にならないように\(a \ge b\)としました。

しかし、\(b \ge a\)ならば\(b – a\)とするだけです。

大小関係を考慮せずに済むために、絶対値を使います。

その結果、\(\gcd{(a, b)} = \gcd{(|a – b|, \min{(a, b)})}\)となるのです。

最後に、そもそも\(a\)と\(b\)は奇数を想定しているので\(a – b\)は必ず偶数になります。

つまり、\(a – b\)は偶数で\(\min{(a, b)}\)は奇数です。

先ほど、\(a\)が偶数かつ\(b\)が奇数ならば\(\gcd{(a, b)} = \gcd{(\frac{a}{2}, b)}\)を確認しました。

よって、\(\gcd{(a, b)} = \gcd{(\frac{|a-b|}{2}, \min{(a, b)})}\)となるのです。

プログラム

バイナリ・ユークリッドの互除法の考案には、処理が遅い剰余演算子%の使用を回避するという背景もありました。

(私の環境ではまったく遅いとは感じませんが・・・。)

したがって、アルゴリズム内で数多く行う\(2\)の乗除算には、*や%を使わずにビット演算子を駆使します。

実装例

binary_gcd関数は、バイナリ・ユークリッドの互除法で\(2\)数の最大公約数を求めます。

def binary_gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a

    a, b = abs(a), abs(b)

    if (a | b) & 1 == 0:  # aとbが偶数の場合
        return binary_gcd(a >> 1, b >> 1) << 1
    if a & 1 == 0:  # aが偶数の場合
        return binary_gcd(a >> 1, b)
    if b & 1 == 0:  # bが偶数の場合
        return binary_gcd(a, b >> 1)
    
    return binary_gcd(abs(a - b) >> 1, min(a, b))  # aとbが奇数の場合

実行例です。

num1 = 527
num2 = 341

result = binary_gcd(num1, num2)
print(result)
# 31

解説

恐らく多くの方がこの条件式を疑問に思ったのではないでしょうか。

    if (a | b) & 1 == 0:  # aとbが偶数の場合

実質的に下の記述と同じですが、なぜ判定が可能なのかを解説します。

    if a % 2 == 0 and b % 2 == 0:  # aとbが偶数の場合

まずはビット演算子を軽く復習しましょう。

以上を踏まえ、まずは偶数を\(2\)進数にすると最下位ビットが必ず\(0\)になる事実に着目します。

0010  # 10進数で2
0100  # 10進数で4
0110  # 10進数で6
1000  # 10進数で8
1010  # 10進数で10

仮にどちらも偶数の場合、ビット単位論理和で最下位ビットは必ず\(0\)です。

ビット単位論理和 (4 | 10)

0100  # 10進数で4
1010  # 10進数で10
---
1110  # 10進数で14

そして、今度は先ほどの\(1110\)と\(1\)でビット単位論理積を取ると、結果は必ず\(0\)です。

ビット単位論理積 (14 & 1)

1110  # 10進数で14
0001  # 10進数で1
---
0000  # 10進数で0

つまり、どちらも偶数の場合は、一連の計算の結果は\(0\)になります。

再度コードに戻りましょう。

まずは、\(a\)と\(b\)のビット単位論理和を取り、その結果と\(1\)とのビット単位論理積を取ります。

       (a | b) & 1

この結果が\(0\)であれば偶数なので、判定は次のようになるのです。

    if (a | b) & 1 == 0:  # aとbが偶数の場合

上記が理解できれば、その後の条件式も同じ理屈です。

    if a & 1 == 0:  # aが偶数の場合
        ・・・
    if b & 1 == 0:  # bが偶数の場合
        ・・・

また、左ビットシフト<<は\(10\)進数だと\(2\)倍する計算です。

反対に、右ビットシフト>>は\(10\)進数で\(\frac{1}{2}\)倍する計算です。

        return binary_gcd(a >> 1, b >> 1) << 1

左ビットシフトと右ビットシフトが、それぞれなぜ\(2\)倍・\(\frac{1}{2}\)倍なのかは後日記事にします。

記事になるのを待つよりもググった方が早いかもしれません。

いかがでしょうか。

再度アルゴリズムとコードを確認すると、より理解が深まると思います。

\(2\)数の最大公約数を求めるプログラムの応用

これまで作った\(2\)数の最大公約数を求めるプログラムを応用しましょう。

本記事では、次の事例を紹介します。

\(3\)つ以上の最大公約数を求める

\(3\)つ以上の自然数の最大公約数を求める

\(3\)つ以上の自然数であっても、考え方は先ほどと同様です。

例えば、\(18\)と\(24\)と\(33\)で考えましょう。

一気に\(3\)つ考えると大変なので、まずは\(18\)と\(24\)の最大公約数(\(\gcd{(18, 24)}\))から求めます。

そして最後に\(\gcd{(18, 24)}\)と\(33\)の最大公約数を求めるという流れです。

\(18\)と\(24\)の最大公約数は\(6\)ですね。

次に、\(6\)と\(33\)の最大公約数を考えますが、\(6\)では\(33\)を割り切れません。

しかし、\(6\)の約数である\(3\)だと\(33\)を割り切れます。

ということは、\(3\)ならば\(18\)と\(24\)と\(33\)をすべて割り切れます。

これ以上に大きな公約数は存在しないため、\(3\)が最大公約数です。

今の話を一般化しましょう。

\(3\)つの自然数\(a_1\), (a_2\), \(a_3\)の最大公約数を求める過程は、次のようになります。

\(4)つの自然数\(a_1\), (a_2\), \(a_3\), \(a_4\)の場合です。

そして\(n\)数間の場合です。

これをプログラムに落とし込んでいきます。

プログラム

以下は、\(3\)つ以上の自然数の最大公約数を求めるgcd関数です。

def gcd(*numbers):
    # 引数が渡されていない場合に0を返す
    if not numbers:
        return 0
    
    # 最初の数を gcd_result に代入
    gcd_result = numbers[0]

    # 2番目以降の数について順に最大公約数を計算
    for num in numbers[1:]:
        gcd_result = euclidean_gcd(gcd_result, num)

    # 最終的な最大公約数を返す
    return gcd_result

先生

for文内でeuclidean_gcd関数を使っています。

代わりにbinary_gcd関数でも構いません。

実行例です。

print(gcd_multiple(24, 36, 48))  # 結果: 12
print(gcd_multiple(54, 24, 81))  # 結果: 3

まとめ

今回は、最大公約数を求めるアルゴリズムを\(2)つご紹介しました。

\(1\)つ目は、ユークリッドの互除法です。

\(2\)つ目は、バイナリ・ユークリッドの互除法です。

なお、本記事では関数を作りましたが、
実は最大公約数を求める関数はPythonの標準ライブラリに既にあります。

ですが、プログラミング上達の鍵は実際にコードを書くことにあります。

実際にご自身の手で書くことで、アルゴリズムへの理解もグッと深まるはずです。

最後までご覧いただき、ありがとうございました。