参考:
https://www.cnblogs.com/yxym2016/p/12969067.html
https://blog.csdn.net/weixin_43846904/article/details/112999660

1、暴力求解

已知两个数a,b,i 从1遍历到min(a,b),判断 i 是不是a,b的因数,在遍历过程中找到最大的因数,即为最大公因数。

def gcd(a,b):
    num = 1
    for i in range(2,min(a,b)+1):
        if a%i==0 and b%i==0:
            num = i
    return num

a = int(input('input number a:'))
b = int(input('input number b:'))
print("最大公约数为:",gcd(a,b))

2、辗转相除法

辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。

对于任意给定的两个自然数,假设a>b,
判断b是否为0:如果为0,则最大公约数直接就是a;如果不为0,就将两个整数a与b进行相除。
如果余数为0(a%b==0),则b为两数的最大公约数;如果不等于0,则将b赋值给a,将余数赋值给b,再对新的a、b进行递归运算求最大公约数。
递归的结束条件就是b==0。

def gcd(a,b):
    if a==b:
        return b
    if a<b:
        tmp = b
        b = a
        a = tmp
    if b==0:
        return a
    else:
        num = a%b
        if num==0:
            return b
        else:
            a = b
            b = num
            return gcd(a,b)


a = int(input('a='))
b = int(input('b='))
print('最大公约数为:',gcd(a,b))

3、更相减损法

这个思想起源于我国古代的《九章算术》。

对于任意给定的两个正整数a、b,要求出他们的最大公约数,首先判断他们俩是否都是偶数(能被2整除),如果都是偶数则一直除以2约简,直至不能再被2整除;

如果不是,则用较大的数减去较小的数,然后将所得的差值赋值给原先拥有较大值的那个变量,再拿这个变量与较小值的那个变量进行比较,继续用二者中较大的减去较小的,直到两个变量相等;

最后,将第一步约简掉的2依次乘以第二步得到的“等数”就是最大公约数。

def gcd(a,b):
    ggcd = 1
    num = 0 # 公因数2的数量
    
    # 是否偶数,除以2
    while a%2==0 and b%2==0:
        a = a/2
        b = b/2
        num+=1
        
    # 找“等数”
    while a!=b:
        tmp = max(a,b)-min(a,b)
        b = min(a,b)
        a = tmp
    
    # 求最大公因数
    ggcd = a
    for i in range(0,num):
        ggcd*=2
    return int(ggcd)

a = int(input('a='))
b = int(input('b='))
print('最大公约数为:',gcd(a,b))
Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐