Python如何求公约数
时间: 2023-11-05 12:38:43 浏览: 33
要求两个正整数的最大公约数,可以使用辗转相除法(又称欧几里得算法)。
具体步骤如下:
1. 设较大的数为a,较小的数为b。
2. 用a除以b,得到余数c(0 ≤ c < b)。
3. 若c为0,则b即为最大公约数。
4. 若c不为0,则用b除以c,得到余数d(0 ≤ d < c)。
5. 不断重复步骤3和4,直到得到余数为0为止。
Python 实现代码如下:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
其中,a和b为正整数,函数返回它们的最大公约数。
相关问题
Python求公约数,由用户输入两个正整数,输出这两个正整数的所有公约数
可以使用辗转相除法求两个数的最大公约数,然后通过循环找到它们的所有公约数。
代码如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
num1 = int(input("请输入第一个正整数:"))
num2 = int(input("请输入第二个正整数:"))
# 求最大公约数
g = gcd(num1, num2)
# 找到所有公约数
factors = []
for i in range(1, g + 1):
if g % i == 0:
factors.append(i)
print("最大公约数为:", g)
print("所有公约数为:", factors)
```
输出结果:
```
请输入第一个正整数:12
请输入第二个正整数:18
最大公约数为: 6
所有公约数为: [1, 2, 3, 6]
```
python求最大公约数
好的,您可以使用Python中的math模块来求最大公约数。以下是使用math.gcd()函数来计算最大公约数的Python代码示例:
```
import math
num1 = 36
num2 = 48
gcd = math.gcd(num1, num2)
print("最大公约数为:", gcd)
```
输出:
```
最大公约数为: 12
```
在这个例子中,我们首先导入了Python的math模块,然后定义了两个整数变量num1和num2。然后,我们使用math.gcd()函数计算num1和num2的最大公约数,并将结果存储在一个名为gcd的变量中。最后,我们使用print()函数打印最大公约数的值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)