python中求最大公约数的三种方法

在计算机编程中，代码中会显示出很多的数学算法，数学算法可以通过最小的付出，完成最多的工作。如果我们想要做一件事情，会规划好行动步骤，而算法，就是你所编程序的执行步骤。算法是计算机程序的灵魂，是程序的精髓所在，程序执行效率的高低直接取决于算法的优劣。下面，小编就交给大家几种在python中求取公约数的方法。

几个整数同时均能整除的整数.如果一个整数同时是几个整数的约数,称这个整数为它们的“公约数”;公约数中称为公约数

方法一：辗转相除法

(1)比较两数，并使m>n

(2)将m作被除数，n做除数，相除后余数为r

(3)循环判断r，若r==0，则n为公约数，结束循环。若r!=0，执行m=n，n=r;将m作被除数，n做除数，相除后余数为r

代码：

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

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

m=max(num1,num2)

n=min(num1,num2)

r=m%n

whiler!=0:

m=n

n=r

r=m%n

print(num1,"和",num2,"的公约数为",n)

方法二：辗转相减法

(1)如果p>q，p=p-q

(2)如果q>p，q=q-p

(3)假如p=q，则p或q是公约数

(4)如果p!=q,则继续继续相减，直至p=q

代码：

deffuc2(p,q):

whilep!=q:

ifp>q:

p=p-q

else:

q=q-p

returnp

方法三：枚举法

代码：

#枚举法

deffun3(a,b):

p=a*b

t=a#将a值赋给t

whilet>0:

ifa%t==0andb%t==0:#若a除以t的余数和b除以t的余数都为0时，跳出循环

break

t=t-1#t>0时，每循环一次，t值减一

print("枚举法得公约数为：",t)#当跳出循环时，输出t值即为公约数

#用枚举法求三个正整数的公约数

deffun4(a,b,c):

p=a*b*c

ifa

min=a

else:

min=b

ifmin>c:

min=c#找出输入的a,b,c三个数中的最小的数赋给min

whilemin>0:

ifa%min==0andb%min==0andc%min==0:#若a除以的余数和b除以min的余数和c除以min都为0时，跳出循环

break

min=min-1#>0时，每循环一次，min值减一

print("枚举法得三个数的公约数为：",min)#当跳出循环时，输出min值即为公约数

以上内容为大家介绍了python中求最大公约数的三种方法，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注IT培训机构:千锋教育。

声明：本站部分稿件版权来源于网络，如有侵犯版权，请及时联系我们。