欧几里得算法

​

先给出欧几里得算法的定理：

给定两个整数a和b，设，则a和b的最大公因子等于b和的最大公因子。即 其中， 表示用a除以b所得的余数r。

下面给出欧几里得算法的递归实现：

a=int(input("输入a"))
b=int(input("输入b"))
def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)

print(gcd(a,b))

欧几里得算法的迭代实现：

a=int(input("输入a"))
b=int(input("输入b"))
def gcd(a,b):
    if(b==0):
        return a
    while(a>0):
        c=a%b;a=b;b=c;
        return a

print(gcd(a,b))