求m和n的最大公约数最小公倍数
时间: 2024-06-13 17:05:23 浏览: 12
Python可以通过递归和非递归算法来求两个数的最大公约数和最小公倍数。其中,最大公约数可以使用辗转相除法来实现,最小公倍数可以通过两数相乘再除以它们的最大公约数来实现。具体实现方法如下:
```python
# 求最大公约数的递归算法
def gcd_recursive(m, n):
if n == 0:
return m
else:
return gcd_recursive(n, m % n)
# 求最大公约数的非递归算法
def gcd_iterative(m, n):
while n != 0:
r = m % n
m = n
n = r
return m
# 求最小公倍数
def lcm(m, n):
return m * n // gcd_recursive(m, n)
# 示例
m = 24
n = 36
print("最大公约数:", gcd_recursive(m, n))
print("最大公约数:", gcd_iterative(m, n))
print("最小公倍数:", lcm(m, n))
```
相关问题
输入m,n求最大公约数和最小公倍数c语言
以下是求最大公约数和最小公倍数的C语言代码:
```c
#include <stdio.h>
int main()
{
int m, n, i, gcd, lcm;
printf("Enter two positive integers: ");
scanf("%d %d", &m, &n);
// 求最大公约数
for(i=1; i<=m && i<=n; ++i)
{
if(m%i==0 && n%i==0)
gcd = i;
}
// 求最小公倍数
lcm = m*n/gcd;
printf("Greatest common divisor of %d and %d is %d\n", m, n, gcd);
printf("Least common multiple of %d and %d is %d\n", m, n, lcm);
return 0;
}
```
运行结果:
```
Enter two positive integers: 12 30
Greatest common divisor of 12 and 30 is 6
Least common multiple of 12 and 30 is 60
```
输入m,n,求其最大公约数和最小公倍数
输入两个正整数m和n,求它们的最大公约数和最小公倍数。最大公约数是指能够同时整除m和n的最大正整数,最小公倍数是指m和n的公共倍数中最小的一个。
求最大公约数的方法有很多种,其中一种常用的方法是辗转相除法。具体步骤如下:
1. 如果m小于n,则交换m和n。
2. 用n去除m,得到余数r。
3. 如果r等于0,则n就是最大公约数。
4. 如果r不等于0,则用n去除r,得到余数r1。
5. 重复步骤3和4,直到余数为0为止,此时n就是最大公约数。
求最小公倍数的方法也有很多种,其中一种常用的方法是利用最大公约数求解。最小公倍数等于两数之积除以它们的最大公约数。
因此,最大公约数和最小公倍数的计算公式如下:
最大公约数:gcd(m,n)
最小公倍数:lcm(m,n) = m * n / gcd(m,n)
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)