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

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

我是猫妹，一名爱上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求最大公约数

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

步骤如下：

1. 用较大的数除以较小的数，得到商和余数。
2. 如果余数为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))

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

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

我是猫妹，咱们下次见！