编写函数,利用辗转相除法求两个自然 数的最大公约数,并利用该两数求25与45的最大公约数,36与12的最大公约数。
时间: 2023-12-18 22:47:43 浏览: 34
以下是求最大公约数的Python程序:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(25, 45)) # 输出5
print(gcd(36, 12)) # 输出12
```
其中,`gcd`函数利用辗转相除法求两个自然数的最大公约数。在每一次循环中,将较小的数赋值给b,将a%b的结果赋值给a,直到b等于0为止,此时a的值即为最大公约数。最后,我们分别调用`gcd`函数求25和45的最大公约数,以及36和12的最大公约数。
相关问题
编写一个函数,该函数使用辗转相除法求出两个数的最大公约数
好的,下面是实现辗转相除法求两个数的最大公约数的 Python 代码:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
其中,参数 `a` 和 `b` 分别表示需要求最大公约数的两个数,`while` 循环中,我们不断对 `a` 和 `b` 进行取模操作,直到 `b` 等于 0,此时 `a` 就是最大公约数。最后返回 `a` 即可。
使用方法:
```python
>>> gcd(24, 36)
12
>>> gcd(13, 17)
1
>>> gcd(48, 60)
12
```
注意,这个函数只能接受两个整数作为参数,如果参数不是整数或者参数个数不为 2,会抛出异常。
利用辗转相除法求两个整数的最大公因数和最小公倍数
辗转相除法,也称欧几里得算法,是求两个非零整数最大公约数的一种方法。其基本思想是用较大的数除以较小的数,然后用余数代替较大的数,继续进行相同的操作,直到余数为零为止。此时,较小的数即为这两个数的最大公约数。
以下是利用辗转相除法求两个整数的最大公因数和最小公倍数的示例代码:
```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()函数用来计算最小公倍数。
例如,对于整数21和14,最大公因数为7,最小公倍数为42,可以通过以下代码计算得出:
```python
a = 21
b = 14
print("最大公因数:", gcd(a,b))
print("最小公倍数:", lcm(a,b))
```
输出结果为:
```
最大公因数: 7
最小公倍数: 42
```