python求最大公约数辗转相除法
时间: 2024-01-05 13:21:06 浏览: 34
以下是使用辗转相除法求最大公约数的Python代码示例:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
x = eval(input("请输入两个整数:"))
result = gcd(x[0], x[1])
print("最大公约数为:", result)
```
这段代码定义了一个名为`gcd`的函数,它接受两个参数`a`和`b`,并使用辗转相除法求出它们的最大公约数。在主程序中,我们通过`eval(input("请输入两个整数:"))`获取用户输入的两个整数,并将它们作为参数传递给`gcd`函数。最后,我们将计算得到的最大公约数打印出来。
相关问题
python最小公倍数和最大公约数辗转相除法
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`函数用于求最小公倍数。
辗转相除法的基本思想是:用较大的数除以较小的数,再用余数去除较小的数,如此反复,直到余数为为止。最后的除数就是最大公约数,而最小公倍数等于两数之积除以最大公约数。
例如,求出30和45的最大公约数和最小公倍数,可以这样调用函数:
```python
>>> gcd(30, 45)
15
>>> lcm(30, 45)
90
```
因此,30和45的最大公约数是15,最小公倍数是90。
求最大公约数使用辗转相除法Python
好的,使用Python实现最大公约数的辗转相除法如下:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
其中,a和b为待求最大公约数的两个正整数。在while循环中,每次将b赋值为a除以b的余数,然后将a赋值为原来的b,直到b等于0为止。最后返回a即为最大公约数。