输入两个正整数m和n,求其最大公约数和最小公倍数(用辗转相除法)。
时间: 2024-11-03 09:22:03 浏览: 53
输入两个正整数m和n求其最大公约数和最小公倍数 (2).pdf
求解两个正整数m和n的最大公约数(GCD,Greatest Common Divisor)和最小公倍数(LCM,Least Common Multiple)可以使用欧几里得算法,也称为辗转相除法。以下是步骤:
1. **最大公约数(GCD)**:
- 欧几里得算法原理:对于两个正整数a和b(其中a >= b),它们的最大公约数等于较小数b和两数余数a mod b的最大公约数。
- 遍历直到余数为0,此时的b就是最大公约数。如果原始a较大,则最终的b即为GCD。
2. **最小公倍数(LCM)**:
- LCM可以用GCD来计算,公式为:(a * b) / GCD(a, b)。
- 先计算出GCD,然后将m和n相乘除以GCD即可得到最小公倍数。
以下是Python代码示例:
```python
def gcd(m, n):
while n != 0:
m, n = n, m % n
return m
def lcm(m, n):
return m * n // gcd(m, n)
# 示例输入
m = int(input("请输入第一个正整数m: "))
n = int(input("请输入第二个正整数n: "))
gcd_result = gcd(m, n)
lcm_result = lcm(m, n)
print(f"最大公约数 (GCD): {gcd_result}")
print(f"最小公倍数 (LCM): {lcm_result}")
```
阅读全文