欧几里得算法又称辗转相除法是一种高效计算两个非负整数最大公约数GCD的算法其核心原理基于gcd(a, b) gcd(b, a mod b)这一关键等式 。算法原理与步骤算法基于以下数论性质两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数 。具体步骤如下对于输入的两个非负整数a和b假设a b若不满足则交换。计算a除以b的余数r即r a % b。若r 0则b即为所求的最大公约数。若r ! 0则令a b,b r并返回步骤2继续执行。此过程循环或递归进行直到余数为零 。代码实现1. 递归实现最简洁def gcd_euclid_recursive(a, b): 使用递归实现欧几里得算法求最大公约数。 :param a: 非负整数 :param b: 非负整数 :return: a和b的最大公约数 if b 0: return a return gcd_euclid_recursive(b, a % b) # 示例 print(gcd_euclid_recursive(48, 18)) # 输出: 6 print(gcd_euclid_recursive(56, 98)) # 输出: 142. 迭代实现效率更优def gcd_euclid_iterative(a, b): 使用迭代循环实现欧几里得算法求最大公约数。 :param a: 非负整数 :param b: 非负整数 :return: a和b的最大公约数 while b ! 0: a, b b, a % b # 同步交换和取余 return a # 示例 print(gcd_euclid_iterative(48, 18)) # 输出: 6 print(gcd_euclid_iterative(56, 98)) # 输出: 14####3. C 实现#include iostream using namespace std; int gcd(int a, int b) { // 迭代实现 while (b ! 0) { int temp b; b a % b; a temp; } return a; } int main() { cout GCD of 48 and 18 is: gcd(48, 18) endl; // 输出: 6 cout GCD of 56 and 98 is: gcd(56, 98) endl; // 输出: 14 return 0; }算法特性与对比特性描述时间复杂度O(log(min(a, b)))在输入为斐波那契数列的相邻两项时达到最坏情况但通常非常高效 。空间复杂度迭代实现为O(1)递归实现为O(log n)递归调用栈深度。核心优势效率远高于枚举法无需对整数进行素因子分解 。输入要求算法要求输入为非负整数。通常约定gcd(a, 0) a。扩展应用计算最小公倍数 (LCM)利用最大公约数可以高效计算最小公倍数公式为lcm(a, b) a * b / gcd(a, b)。def lcm(a, b): 计算两个数的最小公倍数 return abs(a * b) // gcd_euclid_iterative(a, b) # 使用迭代GCD函数 print(lcm(12, 18)) # 输出: 36算法正确性证明简述算法的正确性基于等式gcd(a, b) gcd(b, a - b)的推广。设a b * q r其中q是商r是余数则a和b的公约数集合与b和r的公约数集合完全相同因此它们的最大公约数也必然相等 。参考来源【学习笔记】 欧几里得算法求最大公约数欧几里得算法求最大公约数python,算法欧几里得求最大公约数python版【知识点】欧几里得算法求最大公约数求最大公约数欧几里得算法欧几里得算法求最大公约数