Python实现最大公约数与最小公倍数：递归与非递归算法详解

Noah

发布时间：2026-10-13| 5人浏览过

原创

本文通过Python代码演示了如何计算两个数的最大公约数和最小公倍数。内容涵盖非递归与递归两种算法实现，并对比了Python内置库函数的用法。文中提供了完整的代码示例及运行结果分析，帮助开发者理解算法逻辑并应用于实际开发中。

本文通过Python代码示例，详细讲解了利用递归和非递归两种方式求解两个数值最大公约数及最小公倍数的方法。

最大公约数和最小公倍数的基本概念在此不再赘述。本文记录该代码的初衷源于实际编程任务中的需求，旨在分享解决方案并协助遇到类似问题的读者。具体实现代码如下：

#!/usr/bin/env python
#coding:utf-8
from fractions import gcd
#非递归实现
def gcd_test_one(a, b):
  if a!=0 and b!=0:
    if a>b:
      a, b=b, a
    if b%a==0:
      return a
    gcd_list=[]
    for i in range(1,a):
      if b%i==0 and a%i==0:
        gcd_list.append(i)
    return max(gcd_list)
  else:
    print 'Number is wrong!!!'
#递归实现
def gcd_test_two(a, b):
  if a>b:
    a, b=b, a
  if b%a==0:
    return a
  else:
    return gcd_test_two(a,b%a)
#python自带的gcd
def gcd_test_three(a, b):
  return gcd(a,b)
if __name__ == '__main__':
  print gcd_test_one(12,24)
  print gcd_test_one(12,8)
  print gcd_test_one(6,24)
  print gcd_test_one(0,24)
  print '----------------------------------------------------------------------------'
  print gcd_test_two(12,24)
  print gcd_test_two(12,8)
  print gcd_test_two(6,32)
  print '----------------------------------------------------------------------------'
  print gcd_test_three(12,24)
  print gcd_test_three(12,8)

程序运行输出结果如下所示：

12 4 6 Number is wrong!!! None ---------------------------------------------------------------------------- 12 4 2 ---------------------------------------------------------------------------- 12 4

此外，推荐参考本站提供的在线辅助工具：

在线最小公倍数/最大公约数计算工具： http://tools.jb51.net/jisuanqi/gbs_gys_calc

如需深入了解Python相关技巧，可查阅本站系列教程，包括《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》以及《Python文件与目录操作技巧汇总》。

期望本文提供的代码示例能对读者的Python编程实践有所助益。