Java高效求解两个整数GCD方法

本文介绍如何修正暴力遍历法求最大公约数时重复输出所有公因数的问题，通过变量作用域调整与输出时机优化，确保仅输出最大的那个公约数。

本文介绍如何修正暴力遍历法求最大公约数时重复输出所有公因数的问题，通过变量作用域调整与输出时机优化，确保仅输出最大的那个公约数。

在使用穷举法计算两个正整数的最大公约数（GCD）时，一个常见误区是：将 GCD 变量声明在循环内部，并在每次满足条件时立即打印——这会导致所有公因数（如 1, 2, 5, 10）都被逐个输出，而无法直接获得“最大”的那个。

正确做法是：将 GCD 声明为循环外的局部变量，初始化为 1（最小可能的正公约数），在循环中持续更新其值；待遍历结束后，再统一输出最终结果。由于循环从 i = 1 递增至 min(X, X1)，每次找到新公因数时都会覆盖前值，因此最终保留的必然是最大的那个。

以下是修正后的完整代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Please Enter Your Integer");
        int X = input.nextInt();
        int X1 = input.nextInt();

        int GCD = 1; // 初始化为最小正公约数
        for (int i = 1; i <= X && i <= X1; i++) {
            if (X % i == 0 && X1 % i == 0) {
                GCD = i; // 动态更新为当前找到的公因数（自然递增，故最后即最大）
            }
        }

        System.out.printf("GCD of %d and %d is: %d\n", X, X1, GCD);
        input.close(); // 推荐显式关闭Scanner，避免资源泄漏
    }
}

⚠️ 注意事项：

• 此方法时间复杂度为 O(min(X, X1))，适用于小数值场景；对于大数，建议改用更高效的 欧几里得算法（辗转相除法），例如：

  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

• 输入未做合法性校验（如负数、零），实际项目中应添加 if (X <= 0 || X1 <= 0) 等健壮性判断；
• Scanner 使用后及时调用 close() 是良好实践，防止潜在的资源占用问题。

总结：核心在于理解“最大公约数是满足条件的最后一个 i”，因此只需延迟输出、集中赋值，无需反转循环或引入额外数据结构。