用Python求最大公约数,最大公约数怎么求算法python

　　求最大公约数是习题中常见的类型。本文将为您提供五种常用算法，它们都是用Python实现的。感兴趣的朋友可以看看。

　　00-1010方法一：短除法方法二：欧几里德算法(交替除法)方法三：多减法方法四：穷举法(枚举法)方法五：斯坦算法求最大公约数是习题中常见的一种类型。下面小编就为大家提供五种常用算法。记得给我点个赞！

　　一般来说，求最大公约数大概有五种方法。

目录

　　短除法是一种求最大公因式的方法，也可以用来求最小公倍数。求几个数的最大公因式的方法是从观察法和比较法开始的，即先求出每个数的因子，再求出公因式，最后求出公因式中的最大公因式。之后用因式分解素因子法分别分解两个数的因子，然后进行运算。然后演变成短分裂。短除法是用一个除数除以一个能被它整除的素数，以此类推，直到两个数的商是一个素数。

　　简单来说就是逐步找出两个数的所有公约数，然后将这些公约数相乘得到最大公约数！

　　a=int(input(请输入第一个数字：))

　　b=int(input(请输入第二个数：))

　　m，n=a，b #创建两个变量来存储A和b。

　　T=1 #创建T作为最大公约数的载体

　　对于范围(2，min(a，b)):中的I

　　while (a%i==0，b%i==0):

　　T*=i #所有的公约数相乘在一起。

　　a/=i

　　b/=i

　　print(f { m }，{n}的最大公约数是：{t} ))

　　这种方法虽然有点麻烦，但是逻辑清晰，不容易出错。

方法一：短除法

　　欧几里德算法用于求两个正整数的最大公约数。古希腊数学家欧几里德在他的著作《The Elements》中首次描述了这种算法，因此将其命名为欧几里德算法。

　　如果需要两个正整数1997和615的最大公约数，则使用欧几里德算法，具体如下：

　　1997/615=3 152

　　615/152=4 7

　　152/7=21 5

　　7/5=1 2

　　5/2=2 1

　　2/1=2 0

　　到目前为止，最大公约数是1。

　　用除数和余数重复除法运算。余数为0时，取当前公式的除数为最大公约数，则1997和615的最大公约数为1。

　　知道了逻辑，就可以开始写程序了！

　　a=int(input(请输入第一个数字：))

　　b=int(input(请输入第二个数：))

　　#首先将两个数排序，确保大的数除以小数。

　　m=最大值(a，b)

　　n=最小值(a，b)

　　t=m%n

　　while t！=0:

　　M，n=n，t #仔细观察不难发现：每个除法公式的M和N都是前一个公式的N和余数。

　　T=m%n #更新余数

　　print(f { a }和{b}的最大公约数是{n} )

　　当然，递归的方法也可以实现欧几里德算法。

　　def GCD(a，b):

　　#比较大小以确保大数被小数除

　　如果ab:

　　a，b=b，a

　　#判断是否可分，如果可分，直接返还红利。

　　如果a%b==0:

　　返回b

　　#如果不能整除，则返回函数GCD，并相应地改变参数。

　　else:

　　返回GCD(b

　　,a%b)

　　a=int(input("please input the first number："))

　　b=int(input("please input the second number："))

　　gcd=GCD(a,b)

　　print(f"{a}和{b}的最大公约数为{gcd}")

方法三：更相减损术

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

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

　　白话文译文：

　　（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用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)
　　# 判断两数是否都是偶数，如果都是偶数就同时除2
　　while m%2==0 and n%2==0:
　　 m,n=m/2,n/2
　　t=m-n
　　# 判断条件是减数和差相等
　　while n!=t:
　　 m,n=max(n,t),min(n,t) # 每减一轮之后，都要重新判断减数和差的大小，再次以大数减去小数
　　 t=m-n
　　print(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}")

　　以上就是Python实现求解最大公约数的五种方法总结的详细内容，更多关于Python求最大公约数的资料请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。