键盘输入两个数,编写两个函数分别计算最大公约数和最小公倍数(可以使用穷举法)
时间: 2023-04-07 08:00:42 浏览: 50
好的,这是一个计算问题,我可以回答。以下是两个函数的代码:
```
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)
```
其中,gcd 函数使用了辗转相除法来计算最大公约数,lcm 函数则使用了最大公约数来计算最小公倍数。
相关问题
分别使用辗转相除法和穷举法求两个整数的最大公约数和最小公倍数
【辗转相除法】
辗转相除法又叫欧几里得算法,是求两个正整数的最大公约数的一种方法。它的基本思想是用较小的数除较大的数,再用出现的余数去除除数,不断重复这个过程,直到余数为零为止。最后的除数就是这两个数的最大公约数。
求两个整数a和b的最大公约数的辗转相除法公式如下:
gcd(a,b) = gcd(b,a%b)
其中,a%b表示a除以b所得的余数,gcd(a,b)表示a和b的最大公约数。
代码实现:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
【穷举法】
穷举法是一种简单直观的方法,它的基本思想是列举出所有可能的公约数,然后找出其中最大的一个。求两个整数a和b的最大公约数的穷举法公式如下:
gcd(a,b) = max({i | i是a的因数 且 i是b的因数})
其中,i是a和b的公约数,max表示取其中的最大值。
代码实现:
```python
def gcd(a, b):
res = 1
for i in range(1, min(a, b) + 1):
if a % i == 0 and b % i == 0:
res = i
return res
```
最小公倍数的求法:
根据最大公约数的定义,有以下公式:
lcm(a,b) = a * b / gcd(a,b)
其中,lcm表示a和b的最小公倍数。
代码实现:
```python
def lcm(a, b):
return a * b // gcd(a, b)
```
用暴力穷举法求两数的最大公约数和最小公倍数
暴力穷举法是一种简单粗暴的算法,可以用来求解两个数的最大公约数和最小公倍数。具体实现方法如下:
最大公约数(GCD)的求解方法:
1. 从两个数中较小的数开始,逐个往下枚举,找到两个数都能整除的最大的数,即为最大公约数。
2. 如果两个数中有一个数为0,则另一个数即为最大公约数。
最小公倍数(LCM)的求解方法:
1. 先求出最大公约数。
2. 两个数的乘积除以最大公约数即为最小公倍数。
下面是C语言的代码实现:
```
#include <stdio.h>
int gcd(int a, int b) {
int i, min, result;
if (a == 0 || b == 0) {
return a + b;
}
min = a < b ? a : b;
for (i = min; i >= 1; i--) {
if (a % i == 0 && b % i == 0) {
result = i;
break;
}
}
return result;
}
int lcm(int a, int b) {
int result;
result = a * b / gcd(a, b);
return result;
}
int main() {
int a, b, GCD, LCM;
printf("请输入两个整数:\n");
scanf("%d%d", &a, &b);
GCD = gcd(a, b);
LCM = lcm(a, b);
printf("%d和%d的最大公约数为:%d\n", a, b, GCD);
printf("%d和%d的最小公倍数为:%d\n", a, b, LCM);
return 0;
}
```