:输入两个正整数m和n,求其最大公约数和最小公倍数
时间: 2023-02-22 18:26:05 浏览: 79
输入两个正整数m和n,求其最大公约数和最小公倍
求两个正整数的最大公约数和最小公倍数的常见方法是使用辗转相除法(Euclidean algorithm)。
辗转相除法的基本思想是:两个数的最大公约数等于其中较小的数与两数相除余数的最大公约数。
所以可以这样做:
1. 设m和n的值分别为m和n,并且m >= n
2. 对m和n取模,计算r = m % n
3. 如果r等于0,则n即为最大公约数
4. 如果r不等于0,则将n的值赋给m,将r的值赋给n,并回到步骤2。
最小公倍数 = m * n / 最大公约数。
代码实现:
```
def gcd(m, n):
while n != 0:
r = m % n
m = n
n = r
return m
def lcm(m, n):
return m * n // gcd(m, n)
```
阅读全文