Python中怎么求最大公约数

一、什么是最大公约数

最大公约数（Greatest Common Divisor，简称GCD），又称最大公因数，指两个或多个整数共有约数中最大的那一个，也就是所有可以同时整除这些整数的最大的那个数。

二、Python求最大公约数的方法

Python中求最大公约数有几种常用的方法，其中最常用的是辗转相除法和欧几里得算法。

三、辗转相除法

辗转相除法（Euclidean Algorithm）是求最大公约数的一种算法，它是由古希腊数学家厄拉多塞（Euclid）提出的，也叫做厄拉多塞算法。它的基本思想是：用较大的数除以较小的数，再用除数除以出现的余数，直到余数为0，所得的最后一个除数就是这两个数的最大公约数。

Python实现辗转相除法求最大公约数的代码如下：

def gcd(x, y):
if x > y:
smaller = y
else:
smaller = x
for i in range(1, smaller+1):
if((x % i == 0) and (y % i == 0)):
gcd = i
return gcd

四、欧几里得算法

欧几里得算法（Euclidean Algorithm）是一种求最大公约数的算法，也叫辗转相除法，它是由古希腊数学家厄拉多塞（Euclid）提出的，它的基本思想是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

Python实现欧几里得算法求最大公约数的代码如下：

def gcd(x, y):
if x == 0:
return y
return gcd(y%x, x)