输入两个正整数m,求其最大公因数和最小公倍数
时间: 2023-11-03 22:12:56 浏览: 112
输入两个正整数m和n,求最小公倍数,与最大公约数.docx
最大公因数可以用辗转相除法,也叫欧几里得算法,来求解。具体步骤如下:
1. 用较大数除以较小数,得到余数r(余数不为0);
2. 用上一步得到的余数r去除上一步的除数,得到新的余数;
3. 重复步骤2,直到余数为0为止,此时除数就是最大公因数。
代码如下:
```python
def gcd(m, n):
while n:
m, n = n, m % n
return m
```
最小公倍数可以用最大公因数来求解,公式为:两数的乘积除以最大公因数。代码如下:
```python
def lcm(m, n):
return m * n // gcd(m, n)
```
完整代码如下:
```python
def gcd(m, n):
while n:
m, n = n, m % n
return m
def lcm(m, n):
return m * n // gcd(m, n)
m = int(input('请输入第一个正整数:'))
n = int(input('请输入第二个正整数:'))
print('最大公因数为:', gcd(m, n))
print('最小公倍数为:', lcm(m, n))
```
阅读全文