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

超有名どころ。最古のアルゴリズムらしいです。

ユークリッドの互除法 - Wikipedia

書いてあるとおりに素直に実装すればいいだけですね。

def gcd(x, y):
    if x<y:
        return gcd(y, x)
    r = y
    while x%y!=0:
        r = x%y
        x, y = y, r
    return r

print(gcd(1029, 1071))

ちなみに一次不定式を解くときに最大公約数が使えるとのことでやってみたのですが

# 連立一次方程式を解く
# Simultaneous linear equations

def sle(m=1071, n=1029):
    stack = []
    def gcd(m, n):
        if m<n:
            return gcd(n, m)
        while m%n!=0:
            r = m%n
            stack.append([n, m//n, r])
            m, n = n, r
        return (r, stack)
    thisisgcd, mystack = gcd(m, n)
    me = ""
    fomula = "{}-{}*{}"
    tmp = fomula
    for target in mystack[::-1]:
        i, j, k = target
        if me is not "":
            f, s = tmp.rfind('('), tmp.find(')')
            tmp = tmp[:f]+"({})"+tmp[s+1:]
        else:
            tmp = fomula.format(i*j+k, "("+str(i)+")", j)
        me = "{}-({})*{}".format(i*j+k, i, j)
        tmp = tmp.format(me)
    print(thisisgcd==eval(tmp))

sle(8, 11)
sle()

ほんとは解を求めたかったのですがやり方がわからず、アルゴリズムの仕組みを浚うさけで終わりました。。解がほしいひとはnumpyでできるらしいっすよ。

[2017/11/03 追記]

python3.5からはmathモジュールにgcdがあるらしいです。知らんかった

9.2. math — Mathematical functions — Python 3.6.5rc1 documentation