辗转相除法求两个正整数最大公约数和最小公倍数的代码python
时间: 2023-11-17 20:04:36 浏览: 85
7-3 最大公约数和最小公倍数.docx
以下是求两个正整数最大公约数和最小公倍数的辗转相除法代码:
```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 为止。此时,较小的数即为最大公约数,较大的数与最大公约数的乘积即为最小公倍数。
阅读全文