使用 Python 程序计算最大公因数(HCF)/最大公约数(GCD)

itomcoil 2025-01-06 13:21 32 浏览

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

使用递归函数

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

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)} ")

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

python辗转相除法求最大公约数

上一篇：从零开始:Python教程之最大公约数求解
下一篇：少儿Python每日一题(8):最大公约数和最小公倍数

使用 Python 程序计算最大公因数(HCF)/最大公约数(GCD)

使用递归函数

利用循环

使用欧几里得算法

使用 math.gcd() 函数

使用 numpy.gcd() 函数

相关推荐

我用 1 个 2 手计算器换了 3 台 MacBook(上)

零基础也能搞定!DeepSeek大模型本地安装全攻略

Win7中同时安装python2和python3的方法

按颜色计数、求和、算平均值或最大值?学这个函数就够啦!

SpringBoot中使用LocalDateTime踩坑记录

FANUC机器人故障诊断-设备名和代码篇

中药古今研究:人参

「mysql第二次安装不了」mysql安装失败怎么清理干净?

RSA 复杂题目 ?

深入理解Python中的try-except语句，避免代码崩溃的噩梦