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

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

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

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

  方法二:辗转相减法

  (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/


返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线