最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

使用递归函数

递归是函数调用自身的一种机制。使用递归程序，用较小的问题来解决较大的问题。它通过自引用表达式调用自身，直到满足定义的条件以返回数字的最大公约数。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
a = 28
b = 72
print(f"{a}和{b}的最大公约数是：{gcd(a,b)} ")

# 输出：
28和72的最大公约数是：4 

利用循环

def GCD(a, b): 
    if a > b: 
        tiny = b 
    else: 
        tiny = a 
    for j in range(1, tiny+1): 
        if (a % j == 0) and (b % j == 0): 
            finalgcd = j         
    return finalgcd 
  
a=28
b=72
print(f"{a}和{b}的最大公约数是：{GCD(a,b)} ")

for 循环变量 j 从 1 开始循环迭代，如果这两个数能同时被 j 整数，j 就是公约数，迭代完毕找到最大公约数。

使用欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。前面使用递归函数计算最大公约数也使用了使用欧几里得算法。

def GCD(a, b): 
   while b != 0: 
       a, b = b, a % b 
   return a 
  
a=28
b=72
print(f"{a}和{b}的最大公约数是：{GCD(a,b)} ")

使用 math.gcd() 函数

math 模块提供了 gcd() 函数，直接计算给定数字的最大公约数。这是计算给定两个数字的最大公约数的最简单快捷的方法。

import math  
a=28
b=72
print(f"{a}和{b}的最大公约数是：{math.gcd(a,b)} ")

使用 numpy.gcd() 函数

numpy 模块中也提供了直接计算给定数字最大公约数的函数。

import numpy
a=28
b=72
print(f"{a}和{b}的最大公约数是：{numpy.gcd(a,b)} ")

?

文章创作不易，如果您喜欢这篇文章，请关注、点赞并分享给朋友。如有意见和建议，请在评论中反馈！

?