求两数的最大公约数的三种方法（python实现）

求两个数的最大公约数，有三种方法，分别是：短除法，辗转相除法，更相减损法。
短除法：
运用短除法找到两个数的最大公约数，具体过程是逐步找出两个数的所有公约数，再把这些公约数累乘起来，就得到两个数的最大公约数。

def func1():
    a = int(input("请输入第一个数："))
    b = int(input("请输入第二个数："))
    a1,b1 = a,b
    t=1
    for i in range(2,min(a,b)):
        while(a % i == 0 and b % i == 0):
            t=t*i
            a=a/i
            b=b/i
    print("%s,%s的最大公约数为：%s" %(a1,b1,t))

if __name__ == '__main__':
    func1()

运行结果：

请输入第一个数：20
请输入第二个数：80
20,80的最大公约数为：20

辗转相除法：
（1）比较两数，并使m>n
（2）将m作被除数，n做除数，相除后余数为r
（3）循环判断r，若r==0，则n为最大公约数，结束循环。若r ！=0 ，执行m=n，n=r；

解释：求两个数的最大公约数时，先用较大数除以较小数，如果能整除，最大公约数就等于较小数；否则用较小数除以第一步的余数，如果能整除，最大公约数就等于第一步的余数；否则，用当前获得的余数除以上一步的余数，直到能整除为止。此时作为除数的那个数就是最开始那两个数的最大公约数。

def func2():
    num1 = int(input("请输入第一个数字："))
    num2 = int(input("请输入第一个数字："))
    m = max(num1, num2)
    n = min(num1, num2)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    print(num1, "和", num2, "的最大公约数为", n)
    
if __name__ == '__main__':
    func2()

运行结果：

请输入第一个数字：20
请输入第一个数字：40
20 和 40 的最大公约数为 20

还可以用该方法求两数的最小公倍数：
定理：两数之积(s) = 最小公倍数(a) * 最大公约数(b)

def func3():
    a = int(input('please enter 1st num:'))
    b = int(input('please enter 2nd num:'))
    s = a * b
    while a % b != 0:
        a, b = b, (a % b)
    else:
        print("最大公约数是：", b)
        print("最小公倍数是：", s // b)

运行结果：

please enter 1st num:30
please enter 2nd num:35
最大公约数是： 5
最小公倍数是： 210

更相减损法：

释义：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”--出自《九章算术》

白话解释： 如果需要对分数进行约分，那么)可以折半的话，就折半(也就是用2来约分)。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来分。
步骤：
第一步: 任意给定两个正整数;判断它们是否都是偶数。若是，则用2约简;若不是则执行第二步。
第二步: 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的"等数"，就是最大公约数。求"等数"的办法是"更相减损"法。
‘’’

def func4():
    a = int(input('please enter 1st num:'))
    b = int(input('please enter 2nd num:'))
    s = a * b
    while a != b:
        if a > b:
            a -= b
        elif a < b:
            b -= a
    else:
        print("最大公约数是：", b)
        print("最小公倍数是：", s // a)

if __name__ == '__main__':
    func4()

运行结果：

please enter 1st num:20
please enter 2nd num:40
最大公约数是： 20
最小公倍数是： 40

若还有别的方法求两个数的最大公约数，请评论告知，互相学习，非常感谢！！！