输入两个整数m和n求最大公约数和最小公倍数
时间: 2024-09-30 18:10:56 浏览: 24
输入两个整数`m`和`n`,求最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM),可以通过欧几里得算法来计算最大公约数,然后利用公式 `GCD(a, b) * LCM(a, b) = |a * b|` 来计算最小公倍数。以下是步骤:
1. **计算最大公约数** (GCD):
- 如果 `n == 0`,则 `GCD(m, n) = m`,因为任何数和0的最大公约数都是该数本身。
- 否则,递归地应用 `GCD(n, m % n)`。
2. **计算最小公倍数** (LCM):
- 使用上面得到的 `GCD` 和原始的 `m` 和 `n` 计算 `LCM`,即 `LCM = (m * n) / GCD(m, n)`。
以下是这个过程的一个简单示例:
```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_value = gcd(m, n)
lcm_value = lcm(m, n)
print(f"最大公约数(GCD): {gcd_value}")
print(f"最小公倍数(LCM): {lcm_value}")
相关问题
c语言输入两个正整数m和n求最大公约数和最小公倍数
为了求解两个正整数m和n的最大公约数和最小公倍数,我们可以使用辗转相除法。具体步骤如下:
```c
#include <stdio.h>
// 求最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// 求最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int m, n;
printf("请输入两个正整数m和n:"); scanf("%d %d", &m, &n);
printf("最大公约数为:%d\n", gcd(m, n));
printf("最小公倍数为:%d\n", lcm(m, n));
return 0;
}
```
输入两个整数m和n求其最大公约数和最小公倍数
输入两个整数m和n,可以使用辗转相除法求解它们的最大公约数,同时可以通过它们的乘积除以最大公约数来求解最小公倍数。具体步骤如下:
1. 读入两个整数m和n。
2. 计算它们的乘积c=m*n。
3. 使用辗转相除法求解它们的最大公约数max,具体步骤为:将m除以n得到余数r1,然后将n除以r1得到余数r2,以此类推,直到余数为0,此时的除数就是最大公约数max。
4. 计算最小公倍数min=c/max。
5. 输出最大公约数和最小公倍数。
下面是一个使用C语言实现的例子:
```c
#include <stdio.h>
#include <math.h>
int main() {
int m, n, c, max, min, tempValue;
printf("请输入两个整数:\n");
scanf("%d %d", &m, &n);
c = m * n;
while (n != 0) {
tempValue = m % n;
m = n;
n = tempValue;
}
max = m;
min = c / max;
printf("最大公约数为:%d\n", max);
printf("最小公倍数为:%d\n", min);
return 0;
}
```
阅读全文