辗转相除求最大公约数python
时间: 2024-06-22 17:01:58 浏览: 12
辗转相除法,也叫欧几里得算法,是求两个正整数最大公约数(Greatest Common Divisor, GCD)的一种经典方法。在Python中,可以通过递归或循环的方式来实现。这里是一个简单的循环版本的代码示例:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 使用方法
a = int(input("请输入第一个正整数: "))
b = int(input("请输入第二个正整数: "))
result = gcd(a, b)
print(f"{a}和{b}的最大公约数是: {result}")
相关问题
辗转相除法求最大公约数Python
辗转相除法,也称为欧几里德算法,是一种用于求解两个整数的最大公约数的方法。它基于以下原理:两个整数a和b(a>b),它们的最大公约数等于b和a%b的最大公约数。
以下是使用Python实现辗转相除法求最大公约数的代码:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 示例
num1 = 24
num2 = 36
result = gcd(num1, num2)
print("最大公约数为:", result)
```
辗转相除法求最大公约数python
可以使用以下代码来实现辗转相除法求最大公约数:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,`a` 和 `b` 分别为要求最大公约数的两个数,`gcd` 函数将会递归调用自身,直到 `b` 为 0,此时 `a` 即为最大公约数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)