发布时间：2022-05-19 09:44:17 人气：48 作者：多测师

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

　　while r != 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

　　代码：

　　def fuc2(p, q):

　　while p!=q:

　　if p>q:

　　p = p - q

　　else:

　　q = q - p

　　return p

　　方法三：枚举法

　　代码：

　　#枚举法

　　def fun3(a,b):

　　p = a*b

　　t = a #将a值赋给t

　　while t>0 :

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

　　break

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

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

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

　　def fun4(a,b,c):

　　p = a*b*c

　　if a

　　min = a

　　else :

　　min = b

　　if min>c :

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

　　while min>0 :

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

　　break

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

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

　　以上内容为大家介绍了python中求最大公约数的三种方法，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注多测师。https://www.e70w.com/xwzx/