先用辗转相除法求最大公约数,再用最大公约数求最小公倍数python
时间: 2023-07-12 07:12:59 浏览: 97
好的,下面是Python代码:
```python
# 定义函数求最大公约数
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)
# 输入两个数
num1 = int(input("请输入第一个数:"))
num2 = int(input("请输入第二个数:"))
# 调用函数求最大公约数和最小公倍数,并输出结果
print("{0}和{1}的最大公约数为:{2}".format(num1, num2, gcd(num1, num2)))
print("{0}和{1}的最小公倍数为:{2}".format(num1, num2, lcm(num1, num2)))
```
执行结果:
```
请输入第一个数:12
请输入第二个数:18
12和18的最大公约数为:6
12和18的最小公倍数为:36
```
相关问题
用辗转相除法求最大公约数和最小公倍数
辗转相除法又称欧几里得算法,可以用于求两个整数的最大公约数。最小公倍数则可以通过最大公约数求得。
假设两个数分别为a和b,不妨设a>b。
- 首先,用a除以b,得到商q和余数r。
- 若r=0,则b即为最大公约数。
- 若r!=0,则用b除以r,得到商q1和余数r1。
- 若r1=0,则r即为最大公约数。
- 若r1!=0,则用r除以r1,得到商q2和余数r2。
- 重复以上步骤,直到rk=0为止,此时r(k-1)即为最大公约数。
最小公倍数可通过最大公约数的公式求得:两数相乘除以它们的最大公约数。
具体实现可以看下面的Python代码:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
a = 48
b = 36
print('最大公约数:', gcd(a, b))
print('最小公倍数:', lcm(a, b))
```
输出结果为:
```
最大公约数: 12
最小公倍数: 144
```
请问这样回答是否满意?
辗转相除法求最大公约数最小公倍数
辗转相除法,也称欧几里得算法,是求解两个数的最大公约数的一种方法。其基本思想是:用较大的数除以较小的数,再用除数除以出现的余数(第一次除法的除数),如此反复,直到余数为零为止。此时,最后的除数即为这两个数的最大公约数。而最小公倍数可以通过两数的乘积除以最大公约数得到。
以下是辗转相除法求最大公约数的代码实现:
```
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);
}
```
阅读全文