使用python实现简单的欧几里得算法

欧几里得算法的原理：

① X←a；Y←b；

② 如果Y=0，则输出X=gcd(a, b)；

③ R←X (mod Y)；

④ X←Y；

⑤ Y←R；

⑥ 转到②。

例如：a = 3371 ，b = 1435 ，gcd（a，b）

过程如下：

3371 = 1435 + 501
1435 = 501 + 433
501 = 433 + 68
433 = 68 + 25
68 = 25 + 18
25 = 18 + 7
18 = 7 + 4
7 = 4 + 3
4 = 3 + 1
3 = 1 + 0

根据欧几里得算法原理，编写代码如下：

#欧几里得算法
'''
原理：
①  X←a；Y←b；
②  如果Y=0，则输出X=gcd(a, b)；
③  R←X (mod Y)；
④  X←Y；
⑤  Y←R；
⑥  转到②。
'''
#核心算法
def assignment(a,b):
    x = a ; y = b
    while y:
        temp = x
        r = x % y
        x = y
        y = r
        print("%d = %d + %d"%(temp,x,y))  #给出每次计算的步骤，不要可以删除
    return x

a = 3371    # 指定数字，如果要更改可以自行 input
b = 1435
print("过程：")
x = assignment(int(a),int(b))
print()
print("gcd(%d，%d) = %d "%(a,b,x))