欧几里得算法详解（Java语言实现最大公约数计算教程）

Java 实现欧几里得算法（递归版本）

下面是一个使用递归方式实现的欧几里得算法代码：

public class EuclideanAlgorithm {    // 递归实现欧几里得算法    public static int gcd(int a, int b) {        // 确保 a >= b        if (a < b) {            return gcd(b, a);        }                // 基本情况：如果 b 为 0，则 a 就是最大公约数        if (b == 0) {            return a;        }                // 递归调用：gcd(a, b) = gcd(b, a % b)        return gcd(b, a % b);    }    public static void main(String[] args) {        int num1 = 48;        int num2 = 18;        System.out.println("gcd(" + num1 + ", " + num2 + ") = " + gcd(num1, num2));        // 输出：gcd(48, 18) = 6    }}

Java 实现欧几里得算法（迭代版本）

除了递归，我们也可以用循环（迭代）的方式来实现，这样可以避免递归带来的栈溢出风险：

public class EuclideanAlgorithmIterative {    // 迭代实现欧几里得算法    public static int gcd(int a, int b) {        while (b != 0) {            int temp = b;            b = a % b;            a = temp;        }        return a;    }    public static void main(String[] args) {        int num1 = 56;        int num2 = 42;        System.out.println("gcd(" + num1 + ", " + num2 + ") = " + gcd(num1, num2));        // 输出：gcd(56, 42) = 14    }}

为什么欧几里得算法如此高效？

欧几里得算法的时间复杂度为 O(log(min(a, b)))，这意味着即使处理非常大的数字，它也能在极短时间内完成计算。这也是为什么它被广泛应用于密码学、数论和各种工程领域。

总结

通过本教程，你已经学会了：

• 什么是最大公约数；
• 欧几里得算法的基本原理；
• 如何用 Java 编写递归和迭代两种版本的Java实现欧几里得算法；
• 理解了辗转相除法为何高效。

现在你可以自信地在面试或项目中使用这个经典算法了！如果你觉得有帮助，不妨动手敲一遍代码，加深理解。

记住：掌握基础算法是成为优秀程序员的第一步！