Pythonで学ぶユークリッドの互除法

  • URLをコピーしました!

このアルゴリズムの解説に自然数AとBの最大公約数を求める問題を扱います。 単純な方法で計算すると時間がかかってしまいます。 しかし、 ユークリッドの互除法を使うと、計算量O (log (A+B)) で答えが求められます。 アルゴリズムの紹介に加え、計算量にlogが出てくる理由を解説します。

目次

最大公約数・最小公倍数

2つ以上の正の整数に共通する約数 (公約数) の中で最大のものを最大公約数といいます。たとえば6と9の最大公約数は3です。 これは6の約数が 「1,2,3,6」 9の約数が 「1,3,9」 であり、共通する最大の数は3であるからです。

一方、2つ以上の正の整数に共通する倍数 (公倍数) の中で最小のものを最小公倍数といいます。たとえば6と9の最小公倍数は18です。 これは6の倍数が 「6,12,18,24,309の倍数が 「9, 18, 27, 36,45,…」 と続き、 共通する最小の数は18であるからです。

2つの正の整数a,bには以下の性質が成り立つため、最大公約数と最小公倍数のうち片方でも分かれば、もう片方は簡単に計算することができます。

a x b = (aとbの最大公約数)×(aとbの最小公倍数)

そして最大公約数はユークリッドの互除法により効率的に計算することができます 

単純なアルゴリズム

まず、33と88の最大公約数を計算してみましょう。明らかに答えは33以下です。そこで以下のように「1,2,…,33それぞれについて、33と88両方が割り切れるかどうか」を調べる方法が考えられます。しかし、手計算では答えを求めるのに時間がかかってしまいます。 

最大公約数を求めるプログラム

一般の正の整数 A,Bの最大公約数についても、同じように1からmin (A,B) まで割り切れるかどうかを調べることで求められます。 たとえば次のコードのような実装が考えられます。 しかし余りの計算を 2 × min (A, B) 回行う必要があり、 あまり効率的ではありません。

# 正の整数 A と B の最大公約数を返す関数

# GCD は Greatest Common Divisor(最大公約数)の略

    def GCD(A, B):

    answer = 0

    for i in range(1, min(A, B) + 1):

    if A % i == 0 and B % i == 0:

        answer = i

    return answer

A, B = map(int, input().split())

print(GCD(A, B))

効率的なアルゴリズム:ユークリッドの互除法

実は、以下の方法を使うと、 2つの数の最大公約数を高速に計算することができます。

たとえばこの方法で33と88の最大公約数 123と777の最大公約数をそれぞれ計算すると、計算過程は以下のようになります。 全部確かめる方法に比べ、計算回数が大幅に少ないです。

STEP
1. 大きいほうの数を「大きいほうを小さいほうで割った余り」に書き換えるという操作を繰り返す
STEP
2.片方が0になったら操作を終了する。もう片方の数が最大公約数である

ユークリッドの互除法の実装例

このようなアルゴリズムをユークリッドの互除法といいます。 AとBの最大公約数を求めるときの計算量はO(log (A+B)) であるため、 A, B が 1018程度であっても一瞬で計算できます。

実装の一例としてコード3.2.2が考えられます。 AとBの大小関係によって行うべき操作が変わるので、

if文を用いて場合分けを行っています。 なお、 再帰関数 (3.6節) を用いた賢い実装方法もあります。

# 正の整数 A と B の最大公約数を返す関数

# GCD は Greatest Common Divisor(最大公約数)の略

def GCD(A, B):

    while A >= 1 and B >= 1:

        if A < B:

               B = B % A  # A < B の場合、大きい方 B を書き換える

        else:

               A = A % B  # A >= B の場合、大きい方 A を書き換える

    if A >= 1:

        return A

    returnB

A, B = map(int, input().split())

print(GCD(A, B))

計算回数が log になる理由

次に、計算量がO (log (A+B)) になる理由を考えてみましょう。

まず、「1回の操作でA+Bの値が必ず2/3倍以下に減る」という重要な事実があります。たとえばA=33,B=88の場合の計算過程は次の通りであり、確かに2/3倍以下に減っています。

 

この事実はなぜ成り立つのでしょうか。 A<Bの場合はA,Bを逆にすれば良いので、ここではA≧Bの場合のみ考えます。 

実は、 AとBの差が2倍以上かどうかによって場合分けを行うと、以下の理由により両方2/3倍以下に減っていることが分かります。

・差が2倍未満: 操作によってA+Bの値は 「3B未満」 から Bだけ減る

・差が2倍以上: 操作によってA+Bの値は 「3B以上」から「2B未満」に減る

たとえばBの値を10に固定して考えた場合は以下の通りです。 Aの値が20未満の場合も、 20以上の場合も、必ず2/3倍以下に減っています。

3個以上の最大公約数

3個以上の数の最大公約数も、ユークリッドの互除法によって計算することができます。 具体的なアルゴリズムの流れは次のようになります。

・まず、 1個目の数と2個目の数の最大公約数を計算する

・次に、前の計算結果と3個目の数の最大公約数を計算する

・次に、前の計算結果と4個目の数の最大公約数を計算する

……前の計算結果とN個目の数の最大公約数を計算する (この結果が答え)

たとえば24,40,60,80, 90, 120の最大公約数の計算過程は以下のようになります。なお、3項以上のビット演算と同様、計算順序を入れ替えても計算結果は変わりません。 

この記事が気に入ったら
フォローしてね!

よかったらシェアしてね!
  • URLをコピーしました!
目次