public class CommonDivisor {// 方法1: 使用欧几里得算法 (辗转相除法) - 递归实现 (推荐，简洁高效)public static int greatestCommonDivisorRecursive(int a, int b) {// 确保 a 和 b 都是正数 (公约数只考虑正数)a = Math.abs(a);b = Math.abs(b);if (b == 0) {return a; // 递归终止条件：当 b 为 0 时，a 就是最大公约数} else {return greatestCommonDivisorRecursive(b, a % b); // 递归调用，用 b 和 a 除以 b 的余数继续求最大公约数}}// 方法2: 使用欧几里得算法 (辗转相除法) - 迭代实现 (效率与递归版本相当，避免栈溢出风险)public static int greatestCommonDivisorIterative(int a, int b) {// 确保 a 和 b 都是正数 (公约数只考虑正数)a = Math.abs(a);b = Math.abs(b);while (b != 0) {int temp = b;b = a % b;a = temp;}return a; // 循环结束时，a 就是最大公约数}// 方法3: 暴力枚举法 - 找到所有公约数 (效率较低，但可以找到所有公约数)public static java.util.List commonDivisors(int a, int b) {java.util.List divisors = new java.util.ArrayList;// 公约数不可能大于两个数中较小的那个int smaller = Math.min(Math.abs(a), Math.abs(b));for (int i = 1; i allCommonDivisors = commonDivisors(num1, num2);System.out.println("数字 " + num1 + " 和 " + num2 + " 的所有公约数: " + allCommonDivisors); // 输出: [1, 2, 3, 6]int num3 = 25;int num4 = 5;System.out.println("\n数字 " + num3 + " 和 " + num4 + " 的最大公约数 (递归): " + greatestCommonDivisorRecursive(num3, num4)); // 输出: 5System.out.println("数字 " + num3 + " 和 " + num4 + " 的所有公约数: " + commonDivisors(num3, num4)); // 输出: [1, 5]int num5 = 17; // 质数int num6 = 23; // 质数System.out.println("\n数字 " + num5 + " 和 " + num6 + " 的最大公约数 (递归): " + greatestCommonDivisorRecursive(num5, num6)); // 输出: 1 (互质)System.out.println("数字 " + num5 + " 和 " + num6 + " 的所有公约数: " + commonDivisors(num5, num6)); // 输出: [1]int num7 = -12; // 负数int num8 = 18;System.out.println("\n数字 " + num7 + " 和 " + num8 + " 的最大公约数 (递归): " + greatestCommonDivisorRecursive(num7, num8)); // 输出: 6 (结果为正数)System.out.println("数字 " + num7 + " 和 " + num8 + " 的所有公约数: " + commonDivisors(num7, num8)); // 输出: [1, 2, 3, 6]int num9 = 0;int num10 = 5;System.out.println("\n数字 " + num9 + " 和 " + num10 + " 的最大公约数 (递归): " + greatestCommonDivisorRecursive(num9, num10)); // 输出: 5System.out.println("数字 " + num9 + " 和 " + num10 + " 的所有公约数: " + commonDivisors(num9, num10)); // 输出: [1, 5] (0 和任何非零数的公约数是 非零数的约数)}}步骤:a = Math.abs(a); b = Math.abs(b);: 首先使用 Math.abs 获取 a 和 b 的绝对值，因为公约数通常考虑正数。if (b == 0) { return a; }: 递归终止条件: 如果 b 为 0，则 a 就是最大公约数，直接返回 a。return greatestCommonDivisorRecursive(b, a % b);: 递归调用: 否则，递归调用 greatestCommonDivisorRecursive 方法，参数变为 b 和 a % b ( a 除以 b 的余数)。原理: 同样基于欧几里得算法，但使用迭代 (循环) 的方式实现，避免了递归调用。步骤:a = Math.abs(a); b = Math.abs(b);: 获取 a 和 b 的绝对值。while (b != 0) { ... }: 使用 while 循环，只要 b 不为 0，循环就继续。int temp = b; b = a % b; a = temp;: 循环体内部，实现欧几里得算法的迭代步骤：将 b 的值暂存到 temp 变量。计算 a 除以 b 的余数，并将余数赋值给 b。将 temp (原始的 b 值) 赋值给 a。这样就完成了 a 和 b 值的更新，为下一次迭代做准备。return a;: 当 while 循环结束 (即 b 变为 0) 时，a 中存储的就是最大公约数，将其返回。原理: 从 1 开始，遍历到 a 和 b 中较小的数的绝对值，逐个判断每个数是否同时是 a 和 b 的约数。步骤:java.util.List divisors = new java.util.ArrayList;: 创建一个 ArrayList 来存储找到的公约数。int smaller = Math.min(Math.abs(a), Math.abs(b));: 找到 a 和 b 中绝对值较小的数，公约数不可能大于这个数。for (int i = 1; i : 使用 for 循环，从 1 遍历到 smaller。if (a % i == 0 && b % i == 0) { divisors.add(i); }: 在循环中，判断 i 是否同时能被 a 和 b 整除 (即 a % i == 0 && b % i == 0)。如果能，则 i 是一个公约数，将其添加到 divisors 列表中。return divisors;: 循环结束后，divisors 列表包含了所有公约数，将其返回。摘要：public class CommonDivisor {// 方法1: 使用欧几里得算法 (辗转相除法) - 递归实现 (推荐，简洁高效)public static int greatestCommonDivisorRecursive(int a, int b
在 main 方法中，我提供了示例代码，演示了如何使用这三种方法，并输出了结果，方便你测试和比较。
来源：鸿煊教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!