用Python的辗转相除法求两个数的最大公约数
时间: 2024-02-04 20:44:04 浏览: 34
可以使用以下代码实现辗转相除法求两个数的最大公约数:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
在这个函数中,我们使用一个 while 循环,每次将 b 赋值为 a 除以 b 的余数,同时将 a 赋值为原来的 b,直到 b 等于 0。最后,a 就是最大公约数。
例如,如果我们要求 12 和 18 的最大公约数,调用 gcd(12, 18) 就会返回 6。
相关问题
python for 辗转相除法求两个数的最大公约数
下面是使用 Python 实现辗转相除法求两个数的最大公约数的代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
a = 24
b = 36
print("最大公约数为:", gcd(a, b))
```
输出结果为:
```
最大公约数为: 12
```
代码中,我们使用递归的方式实现了辗转相除法。首先判断 b 是否为 0,如果为 0,则 a 即为最大公约数;否则递归调用 gcd 函数,并将 b 和 a%b 作为参数传递。
使用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` 函数则使用最大公约数求最小公倍数。
相关推荐
![](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)