ユークリッドの互除法とpython3で最大公約数(GCD)を求める

２つの整数の最大公約数を求めるアルゴリズムとしてユークリッドの互除法があります。

２つの整数を割り算して余りを求める操作を繰り返し、余りが0になったら終了するアルゴリズムです。
pythonで2つの整数の最大公約数を求める関数gcd()を実装したのがこちらです。

#!/usr/bin/env python3

def gcd(a, b):
    if a < b:
        t = a
        a = b
        b = t

    last_r = b
    while True:
        c = a // b
        r = a - c * b
        print(str(a)+" = "+str(c)+" * "+str(b)+" + "+str(r))
        if r == 0:
            print("")
            return last_r
        last_r = r
        a = b
        b = r

d = gcd(11921192, 41414141)
print(d)

結果

41414141 = 3 * 11921192 + 5650565
11921192 = 2 * 5650565 + 620062
5650565 = 9 * 620062 + 70007
620062 = 8 * 70007 + 60006
70007 = 1 * 60006 + 10001
60006 = 6 * 10001 + 0

10001

他の結果もみてみましょう。

gcd(100, 4)
100 = 25 * 4 + 0

4

gcd(24, 9)
24 = 2 * 9 + 6
9 = 1 * 6 + 3
6 = 2 * 3 + 0

3

gcd(12345678901234567890, 1122122112212211221222211221112221121)

1122122112212211221222211221112221121 = 90891891907216136 * 12345678901234567890 + 2057480920316748081
12345678901234567890 = 6 * 2057480920316748081 + 793379334079404
2057480920316748081 = 2593 * 793379334079404 + 248307048853509
793379334079404 = 3 * 248307048853509 + 48458187518877
248307048853509 = 5 * 48458187518877 + 6016111259124
48458187518877 = 8 * 6016111259124 + 329297445885
6016111259124 = 18 * 329297445885 + 88757233194
329297445885 = 3 * 88757233194 + 63025746303
88757233194 = 1 * 63025746303 + 25731486891
63025746303 = 2 * 25731486891 + 11562772521
25731486891 = 2 * 11562772521 + 2605941849
11562772521 = 4 * 2605941849 + 1139005125
2605941849 = 2 * 1139005125 + 327931599
1139005125 = 3 * 327931599 + 155210328
327931599 = 2 * 155210328 + 17510943
155210328 = 8 * 17510943 + 15122784
17510943 = 1 * 15122784 + 2388159
15122784 = 6 * 2388159 + 793830
2388159 = 3 * 793830 + 6669
793830 = 119 * 6669 + 219
6669 = 30 * 219 + 99
219 = 2 * 99 + 21
99 = 4 * 21 + 15
21 = 1 * 15 + 6
15 = 2 * 6 + 3
6 = 2 * 3 + 0

3

pythonやrubyはデフォルトで整数の桁が無制限なので、整数論の計算をするのに本当に便利ですね。
まあsageを使うという技もあるのですが、それはまた別の機会にしたいと思います。

これは、じつはウォーミングアップです。
次回は、多項式のGCDを求める関数を実装してみます。