欧几里得算法

算法

欧几里得算法是计算两个非负整数最大公约数(GCD)的经典方法,通过辗转相除法,高效地找出能够同时整除两个数的最大整数。算法基于原理:如果a可以被b整除,最大公约数就是b;否则,gcd(a,b) = gcd(b, a%b)。

时间复杂度:最差 O(log min(a,b))
空间复杂度:O(1)

算法讲解

欧几里得算法

介绍

欧几里得算法(Euclidean Algorithm)是一种计算两个非负整数最大公约数(GCD)的经典算法,也被称为辗转相除法。它由古希腊数学家欧几里得在其著作《几何原本》中首次系统描述,是已知最古老的算法之一,至今已有2300多年的历史。该算法基于一个简单而优雅的原理:两个整数的最大公约数等于其中较小的数与二者相除余数的最大公约数。

算法步骤

  1. 输入两个非负整数a和b
  2. 如果b等于0,则a即为所求的最大公约数
  3. 否则,计算a除以b的余数r
  4. 将b赋值给a,将r赋值给b
  5. 返回步骤2,继续执行,直到b等于0

算法详解

我们以计算252和105的最大公约数为例,展示欧几里得算法的执行过程:

第1步:初始化

  • a = 252, b = 105

第2步:第一次迭代

  • b不等于0,继续执行
  • 计算a除以b的余数:252 ÷ 105 = 2余42

...