用Python求2个正整数的最大公约数
时间: 2024-05-13 07:20:47 浏览: 51
可以使用欧几里得算法(辗转相除法)来求解两个正整数的最大公约数。
代码如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 示例
print(gcd(24, 36)) # 输出:12
```
欧几里得算法的思路是,设两个正整数a和b,令r为a除以b的余数,即r = a % b,若r为0,则b为最大公约数;否则,a = b,b = r,继续进行相同的操作,直到r为0为止。
相关问题
用Python求两个正整数的最大公约数
可以使用欧几里得算法(又称辗转相除法)来求两个正整数的最大公约数。
代码如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 测试
a = 48
b = 60
print(gcd(a, b)) # 输出 12
```
在这个代码中,我们定义了一个函数 `gcd`,它接受两个参数 `a` 和 `b`,返回它们的最大公约数。在函数内部,我们使用递归的方式来实现欧几里得算法。如果 `b` 等于0,那么 `a` 就是最大公约数;否则,我们将 `b` 和 `a` 对 `b` 取模后的结果作为新的参数传入递归调用。
最后,我们测试了一下这个函数,求出了48和60的最大公约数,结果是12。
Python求两个正整数的最大公约数,最小公倍数
在Python中,计算两个正整数的最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)通常可以使用辗转相除法(欧几里得算法)和公式法来实现。
**求最大公约数 (GCD):**
你可以使用math模块中的gcd函数,例如:
```python
import math
a = 48
b = 18
gcd_ab = math.gcd(a, b)
```
如果你需要手动实现,可以使用递归或迭代的方式:
```python
def gcd_iterative(a, b):
while b != 0:
a, b = b, a % b
return a
a, b = 48, 18
gcd_ab_manual = gcd_iterative(a, b)
```
**求最小公倍数 (LCM):**
有了GCD之后,LCM可以用下面的公式计算:`lcm(a, b) = abs(a * b) / gcd(a, b)`。如果想直接计算,也可以使用math模块:
```python
from fractions import gcd as _gcd # 使用内建gcd避免与math.gcd冲突
lcm_ab = abs(a * b) // _gcd(a, b)
# 或者手动计算
def lcm_iterative(a, b):
lcm = max(a, b)
while True:
if lcm % a == lcm % b == 0:
break
lcm += 1
return lcm
lcm_ab_manual = lcm_iterative(a, b)
```
阅读全文