使用辗转相除法求两个正整数的最大公约数,在此基础上计算最小公倍数。python
时间: 2024-04-29 09:22:35 浏览: 18
很高兴回答你的问题。辗转相除法又称欧几里得算法,是求最大公约数的一种简便方法。该算法基于以下定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。即gcd(a,b)=gcd(b,c),其中gcd为最大公约数的函数。我们可以使用while循环实现该算法:
```
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
```
其中gcd函数返回a和b的最大公约数,lcm函数返回a和b的最小公倍数。由于Python中的除法运算是向下取整的,因此我们需要通过//运算符来计算最小公倍数。
相关问题
辗转相除法求两个正整数最大公约数和最小公倍数的代码python
以下是求两个正整数最大公约数和最小公倍数的辗转相除法代码:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
```
其中,`gcd` 函数用于求最大公约数,`lcm` 函数用于求最小公倍数。辗转相除法的思路是用较小的数去除较大的数,然后用余数去除较小的数,一直重复这个过程,直到余数为 0 为止。此时,较小的数即为最大公约数,较大的数与最大公约数的乘积即为最小公倍数。
输入两个正整数,使用辗转相除法求最大公约数和最小公倍数
好的,以下是代码:
```python
def gcd(a, b):
"""
辗转相除法求最大公约数
"""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""
求最小公倍数
"""
return a * b // gcd(a, b)
num1 = int(input("请输入第一个正整数:"))
num2 = int(input("请输入第二个正整数:"))
print("最大公约数为:", gcd(num1, num2))
print("最小公倍数为:", lcm(num1, num2))
```
输入示例:
```
请输入第一个正整数:12
请输入第二个正整数:18
```
输出示例:
```
最大公约数为: 6
最小公倍数为: 36
```
相关推荐
![](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)