当前位置：网站首页 > 技术文章 > 正文

用Python求最大公约数和最小公倍数(51)

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

小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

和猫妹学Python，一起趣味学编程。

今日主题

什么是最大公约数？

如何用Python求最大公约数？

什么是最小公倍数？

如何用Python求最小公倍数？

什么是最大公约数

最大公约数(Greatest Common Divisor,简称GCD)是指两个或多个整数共有约数中最大的一个。

换句话说，如果a和b是两个整数，且a和b的最大公约数为d,则有：

gcd(a, b) = d

其中gcd表示最大公约数。

以下是几个最大公约数的例子：

1. 6和8的最大公约数是2。

2. 9和15的最大公约数是3。

3. 20和30的最大公约数是10。

4. 45和60的最大公约数是15。

5. 72和90的最大公约数是18。

Python求最大公约数

欧几里得算法又称辗转相除法，可以用辗转相除法求最大公约数。

步骤如下：

用较大的数除以较小的数，得到商和余数。
如果余数为0,则较小的数即为最大公约数；否则用较小的数继续除以余数，重复上述步骤。

举例：

1997 ÷ 615 = 3 (余 152)

615 ÷ 152 = 4(余7)

152 ÷ 7 = 21(余5)

7 ÷ 5 = 1 (余2)

5 ÷ 2 = 2 (余1)

2 ÷ 1 = 2 (余0)

Python代码实现：

def gcd(a, b):
    if a == 0:
        return b
    else:
        return gcd(b % a, a)


a = 90
b = 72
print("GCD of", a, "and", b, "is", gcd(a, b))

什么是最小公倍数

最小公倍数(Least Common Multiple,简称LCM)是指两个或多个整数的最小公共倍数。

换句话说，如果a和b是两个整数，且a和b的最小公倍数为lcm,则有：

lcm(a, b) = (a * b) / GCD(a, b)

其中GCD表示最大公约数。

例如，6和8的最小公倍数是24,因为6和8的最小公倍数是它们的乘积除以它们的最大公约数4:

6 * 8 / 4 = 24

因此，6和8的最小公倍数是24。

Python求最小公倍数

def gcd(a, b):
    if a == 0:
        return b
    else:
        return gcd(b % a, a)


def lcm(a, b):
    return a*b/gcd(a,b)


a = 6
b = 8
print("LCM of", a, "and", b, "is", lcm(a, b))

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！

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

上一篇：快来看看:CSS3实现动画的三种方式
下一篇：使用 Python 程序计算最大公因数(HCF)/最大公约数(GCD)

用Python求最大公约数和最小公倍数(51)

相关推荐

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

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

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

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

SpringBoot中使用LocalDateTime踩坑记录

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

中药古今研究:人参

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

RSA 复杂题目 ?

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