最大公約数を求めるアルゴリズム「ユークリッドの互除法」をPythonで解説！

f:id:paiza:20200705215517j:plain
秋山です。Python好きのエンジニアです。

プログラミング問題、特に競技プログラミングで出題される問題の中には、適したアルゴリズムを知っていると比較的楽に答えを導き出せる場合があります。ただ、メジャーなものだけでもたくさんありますし、「どのように学べばいいかよく分からない…」という方もいるかもしれません。

そこで今回は、アルゴリズムの中でも定番の、最大公約数を求める「ユークリッドの互除法」について説明します。

実はユークリッドの互除法は記録に残っている最古（紀元前300年ごろ）のアルゴリズムと言われています。それが現代でも使われているんですよ。

どのようなアルゴリズムなのか説明するだけでなく、Pythonでコードも示しながら解説したいと思います。

ちなみにpaizaラーニングでは、「アルゴリズム入門編」という学習講座を公開しています。フィボナッチ数、ハノイの塔などが学べる内容となっていますので、興味がある方はぜひごらんください。

前提：最大公約数とは

ユークリッドの互除法の説明に入る前に、最大公約数について理解しておく必要があるので簡単に説明します。（最大公約数は小学校の高学年で習いますが、遠い記憶になっている方もいるかもしれないので）

最大公約数とは2つ以上の正の整数の共通の約数のうち最大の数字を言います。約数はある数字を割り切ることのできる整数、またはそれらの集合のことですね。

たとえば、12と18の最大公約数を求めてみます。

12の約数は順に 1, 2, 3, 4, 6, 12 です。

18の約数は順に 1, 2, 3, 6, 9, 18 です。

それぞれの約数の中で最大の数字は6です。よって最大公約数は6となります。

ところで最大公約数を求めて何がうれしいかというと…たとえば、リンゴ12個とミカン18個を同じ個数ずつ箱に入れたいとき、最大公約数「6」が分かると箱が6つあれば均等に分けられることがわかります。

確かに便利ですが……もっとテクノロジー分野の例を出すと、最大公約数は暗号技術で使われています。公開鍵暗号の鍵を作る際は、最大公約数が1である数字（すなわち互いに素である数字）が必要になるためです。

なお、公開鍵暗号については、以下の記事で詳しく解説していますので興味のある方はごらんください。

paiza.hatenablog.com

（参考）互いに素の意味と関連する三つの定理 | 高校数学の美しい物語

最大公約数を求めるアルゴリズム

さて、本題に入りましょう。ここからは与えられた2つの数字の最大公約数を求めるアルゴリズムについて考えてみます。

求める過程を順番に書き出してみると…

正の整数 x と y が入力される
x を 1 ずつ増やしながら x - 1 まで割る。割り切れたら記録する
y を 1 ずつ増やしながら y - 1 まで割る。割り切れたら記録する
記録された割り切れた数の共通を見つける
最大の数を見つける

実際にPythonでコードを書いてみましょう。

def gcd(x, y):
    x_list = []
    y_list = []
    
    cnt = 1
    while x > cnt :
        if x % cnt == 0:
            x_list.append(cnt)
        cnt += 1

    cnt = 1
    while y > cnt:
        if y % cnt == 0:
            y_list.append(cnt)
        cnt += 1

    cnt_x, cnt_y = 0, 0
    gcd_list = []
    for t_x in x_list:
        for  t_y in y_list:
            if t_x == t_y:
                gcd_list.append(t_y)

    return max(gcd_list)

print(gcd(12, 18))

単純なアルゴリズムですがとりあえず答えを求めることができました。

ただこの計算方法だと、与えられた数が小さいときはいいのですが、たとえば x, y が10億ならば10億ループを2回、さらに共通の数を見つけるために割り切れた数同士の数の2乗、そして最大公約数を見つけるための共通の数分の計算が必要となってしまいます。

このアルゴリズムを改善するなら、まず割っていく際に x - 1 まで割る必要はなく、最大で x / 2 までで十分です。共通の数を求める部分も全組み合わせをチェックするところは改善の余地があります。

そこで前述の方法より計算量を抑えて最大公約数を求めるために、今回のメインテーマである「ユークリッドの互除法」というアルゴリズムを説明します。

ユークリッドの互除法では、以下の手順で最大公約数を求めます。

x を y で割り、余り r を求める
y を r で割り、その余り r_1 を求める
r を r_1 で割り、その余り r_2 を求める

（繰り返す）

余りが 0 になったときの割る数が最大公約数

いまいちピンとこないので、さきほども例にした数字を入れて導いてみます。

x = 12、y = 18 とすると、x を y で割った余り r は 12
y = 18 を r = 12 で割った余り r_1 は 6
r = 12 を r_1 = 6 で割った余りは r_2 は 0
よって、このときの割る数「6」が 12 と 18 の最大公約数である

このアルゴリズムのコードは以下のように書くことができます。

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

print(gcd(12, 18))

ユークリッドの互除法のアルゴリズムを使った手順を書いた時点で、割り算の余りを求める単純な繰り返しだなと分かりましたが、再帰を使うとコードはこんなにもシンプルに書けるんです。結果はもちろん最初に書いたコードと同じですよ。

再帰処理は慣れないとちょっと難しいなという印象を持つと思いますが、実際に自分でコードを書きながら理解していきましょう。

ちなみに再帰処理について解説した記事があります。Pythonでプログラミング問題をときながら説明しているので、よければ参考にしてみてください。

paiza.hatenablog.com

ユークリッドの互除法を使うと、計算量も小さいほうの数字の桁数の約5倍繰り返せば必ず答えが出ます。これは「ラメの定理」と呼ばれています。詳しくはこちらのページも参考にしてみてください。

簡単に説明すると、ユークリッドの互除法において余りは必ず小さくなっていきますが、商が 1 ということを繰り返すのが最悪のケース（効率が悪い）となっています。

たとえば以下のようなケースが該当します。

x = 13, y = 8（xをyで割ると商は1、余りは5）
x = 8, y = 5（yをxに、余りをyに設定して同様に商は1、余りは3）
x = 5, y = 3（同様に商は1、余りは2）
x = 3, y = 2（同様に商は1、余りは1）
x = 2, y = 1（同様に商は1、余りは1）
x = 1, y = 0

数学やアルゴリズムが好きな方は気がつくかもしれませんが、これらの数字はフィボナッチ数列となっていることが分かります。

フィボナッチ数列は以下の漸化式で定義されます。

F0 = 0,
F1 = 1,
Fn+2 = Fn + Fn+1 (n ≥ 0)

これを第0項から第21項まで見ていくと…

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ……

フィボナッチ数は、最初の2つが1で、3つめ以降は前の2つを足した値になるのですが、この数字の並び、さきほどの商が1になるケースで出てきた数字ですね。

また、フィボナッチ数列は数字が大きくなればなるほど増え方が大きいことが分かります。最初のいくつかの項までは1桁だった数字が、21項目では10,000を超えています。

ということは逆に考えるとユークリッド互除法では最悪の場合、フィボナッチ数列の大きな数字からさかのぼって小さくなっていくのと同等の回数処理が必要となります。

増え方がどんどん大きくなるものを逆にさかのぼる処理ということは、大きな数字になればなるほど計算回数の増加が抑えられると言えます。

このように考えるとユークリッド互除法が計算量が小さくなることが何となく理解できるかと思います。上のコード例はどちらも12と18の最大公約数を求めていて、あまり計算量が減った恩恵が感じられないので、 print(gcd(12, 18)) の部分を大きな数字に書き換えて実行してみてください。paiza.IOを使うと環境構築なしに試せます。

「フィボナッチ数列はじめて聞いた…」という方は、冒頭でも紹介したpaizaラーニングの「アルゴリズム入門編」で取り上げていますので、よければそちらをごらんください。