欧几里得算法是计算两个非负整数最大公约数(GCD)的经典方法,通过辗转相除法,高效地找出能够同时整除两个数的最大整数。算法基于原理:如果a可以被b整除,最大公约数就是b;否则,gcd(a,b) = gcd(b, a%b)。
欧几里得算法(Euclidean Algorithm)是一种计算两个非负整数最大公约数(GCD)的经典算法,也被称为辗转相除法。它由古希腊数学家欧几里得在其著作《几何原本》中首次系统描述,是已知最古老的算法之一,至今已有2300多年的历史。该算法基于一个简单而优雅的原理:两个整数的最大公约数等于其中较小的数与二者相除余数的最大公约数。
我们以计算252和105的最大公约数为例,展示欧几里得算法的执行过程:
...