用Python求最小公倍数的代码汇总及详解-技术教程-四时宝库

最小公倍数之Python代码汇总及详解

1.摘要

在本文中主要进行以下工作，①首先分析了最小公倍数基本概念，其次针对概念设计方法。②方法1：根据最大公约数来求最小公倍数。③方法2：设置循环计算最小公倍数；④进行拓展可以实现多次最小公倍数计算。最后对每种方法都给出了对应的实例演示及效果。

2.步骤

1.首先我们使用方法1，具体思路为：最小公倍数=两数相乘÷两数的最大公约数，举例子，比如：12和9的最大公因数是3，两数相乘12＊9=108/3=36。36就是12和9的最小公倍数呢。所以，我们首先需要实现求最大公约数，具体代码如下所示。可以先判断输入的a和b的大小，当然也可以不进行判断，无非就是循环中取余的操作会多执行一次。

  # 定义方法求最大公约数 Greatest Common Divisor(GCD)
  def gcd(a, b):
      r = 1 # 余数r
      tmp = 0
      if a < b:
          tmp = a
          a = b
          b = tmp
      while(r != 0):
          r = a % b
          a = b
          b = r
      return a # 此时,a为最后一次相除的除数,即a,b的最大公因数

其中，辗转相除法的算法步骤如下所示。

①第一步，给定两个正整数a，b;

②第二步，计算a除以b所得的余数r ;

③第三步，a＝b，b＝r ;

④第四步，若r＝0，则a，b的最大公约数等于a,否则，返回第二步。

在计算得到最大公约数后，根据最小公倍数=两数相乘÷两数的最大公约数，计算得到最小公倍数，具体代码如下：

  
  # 定义方法求最小公倍数  Least Common Multiple
  def lcm(a, b):
      init_a, init_b = a, b
      r = 1 # 余数r
      tmp = 0
      while(r != 0):
          r = a % b
          a = b
          b = r
      return init_a * init_b // a # 此时,a为最后一次相除的除数,即a,b的最大公因数

运行结果如下所示。如12和15的最小公倍数为60，13和21的最小公倍数为273。

  In [11]: # 定义方法求最小公倍数  Least Common Multiple
      ...: def lcm(a, b):
      ...:     init_a, init_b = a, b
      ...:     r = 1 # 余数r
      ...:     tmp = 0
      ...:     while(r != 0):
      ...:         r = a % b
      ...:         a = b
      ...:         b = r
      ...:     return init_a * init_b // a # 此时,a为最后一次相除的除数,即a,b的最大公因数
      ...:
  
  In [12]: aa = lcm(12, 15)
  In [13]: aa
  Out[13]: 60
  
  In [14]: lcm(12, 15)
  Out[14]: 60
  
  In [15]: lcm(15, 12)
  Out[15]: 60
  
  In [16]: lcm(5, 2)
  Out[16]: 10
  
  In [17]: lcm(13, 21)
  Out[17]: 273

2.对于方法2，具体思路分析如下所示。

①首先我们要获取到输入的两个数的更大者,并定义为greater；

②同时将greater对输入的两个数进行整除，如果同时满足的话,那么就是最小公倍数。

③否则不断对greater加1，直到能够把这两个数整除，也就是找到了最小公倍数。

  
  # 1. 定义计算最小公倍数的方法
  def lcm(a, b): # Least Common Multiple: 最小公倍数
     # 先获取二者之间更大的数
     if a > b:
         greater = a
     else:
         greater = b
     while(True):
         if((greater % a == 0) and (greater % b == 0)):
             lcm = greater
             break
         greater += 1
     return lcm
  # 2. 获取对应输入
  number1 = int(input("请输入数字1: "))
  number2 = int(input("请输入数字2: "))
  result = lcm(number1, number2)
  print( number1,"和", number2,"的最小公倍数为", result)

如下所示，部分运行结果如下所示。

  
  请输入数字1: 12
  请输入数字2: 15
  12 和 15 的最小公倍数为 60
  
  请输入数字1: 13
  请输入数字2: 21
  13 和 21 的最小公倍数为 273

3.再定义了一个简单的求最小公倍数的函数之后，我们在此基础进行拓展，可以让用户求任意一个数的最小公倍数直到停止输入为止。

  
  # 定义方法求最小公倍数  Least Common Multiple
  def lcm(a, b):
      init_a, init_b = a, b
      r = 1 # 余数r
      while(r != 0):
          r = a % b
          a = b
          b = r
      return init_a * init_b // a # 此时,a为最后一次相除的除数,即a,b的最大公因数
  while True:
      choice = int(input("是否继续计算(输入0结束): "))
      if choice == 0:
          break
      else:
          number1 = int(input("请输入数字1: "))
          number2 = int(input("请输入数字2: "))
          result = lcm(number1, number2)
          print( number1,"和", number2,"的最小公倍数为", result)

部分运行结果如下所示。

  
  是否继续计算(输入0结束): 1
  请输入数字1: 12
  请输入数字2: 15
  12 和 15 的最小公倍数为 60
  
  是否继续计算(输入0结束): 1
  请输入数字1: 15
  请输入数字2: 12
  15 和 12 的最小公倍数为 60
  
  是否继续计算(输入0结束): 1
  请输入数字1: 13
  请输入数字2: 21
  13 和 21 的最小公倍数为 273
  是否继续计算(输入0结束):0

四时宝库

程序员的知识宝库

用Python求最小公倍数的代码汇总及详解