Python求最大公约数的五种常见方法

方法三：更相减损术

        更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。原文是：

        可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。     

白话文译文：

（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

        具体步骤：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

        现在使用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

a=int(input("please input the first number："))b=int(input("please input the second number："))#  首先要给两数排序，保证大数减小数m=max(a,b)n=min(a,b)#  判断两数是否都是偶数，如果都是偶数就同时除2while m%2==0 and n%2==0:    m,n=m/2,n/2t=m-n#  判断条件是减数和差相等while n!=t:    m,n=max(n,t),min(n,t) #  每减一轮之后，都要重新判断减数和差的大小，再次以大数减去小数    t=m-nprint(f"{a}和{b}的最大公约数为{n}")

方法四：穷举法（枚举法）

        从两个数中较小数开始，由小到大列举，找出公约数并保证该公约数也属于较大数，这些公约数的最大者就是最大公约数；也可以从大到小列举，直到找出公约数后跳出循环，该公约数即是最大公约数。

a=int(input("please input the first number："))b=int(input("please input the second number："))p,q=min(a,b),max(a,b)lst=[]for i in range(1,p+1):    if p%i==0 and q%i==0:        lst.append(i)gcd=max(lst)print(f"{a}和{b}的最大公约数为{gcd}")#a=int(input("please input the first number："))#b=int(input("please input the second number："))#p,q=min(a,b),max(a,b)#gcd=0#for i in range(p,0,-1):#    if p%i==0 and q%i==0:#        gcd=i#        break#print(f"{a}和{b}的最大公约数为{gcd}")

方法五：Stein算法

        Stein算法是一种计算两个数最大公约数的算法，是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。

欧几里得算法缺陷：

        欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来。

        一般实际应用中的整数很少会超过64位(当然已经允许128位了)，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

看下面两个结论：

        gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
        gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。

        当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数 和一个奇数的最大公约数时，可以先将偶数除以2。

        :param a: 第一个数

        :param b: 第二个数

        :return: 最大公约数

def gcd_Stein(a, b):    #  保证b比a小    if a < b:        a, b = b, a    if (0 == b):        return a    #  a、b都是偶数，除2右移一位即可    if a % 2 == 0 and b % 2 == 0:        return 2 * gcd_Stein(a / 2, b / 2)    #  a是偶数    if a % 2 == 0:        return gcd_Stein(a / 2, b)    #  b是偶数    if b % 2 == 0:        return gcd_Stein(a, b / 2)    #  都是奇数    return gcd_Stein((a + b) / 2, (a - b) / 2)a=int(input("please input the first number："))b=int(input("please input the second number："))gcd=int(gcd_Stein(a,b))print(f"{a}和{b}的最大公约数为{gcd}")

以上就是小编总结的五种常用方法了，希望对各位有所帮助！记得点赞喔！

来源地址：https://blog.csdn.net/m0_69265664/article/details/125708828