如何过滤输出仅显示最大公约数？Java代码优化求助

你的原代码是通过从1开始枚举的方式找公约数，所以会输出所有符合条件的数。要只输出最大公约数，这里给你两种简单可行的方案：

方案1：优化暴力枚举（从大到小找） #

你担心反转循环破坏欧几里得算法逻辑，但其实你的原代码根本没用到欧几里得算法，完全可以放心把遍历方向反过来——从两个数的较小值开始往下找，找到第一个能同时整除两个数的数就是最大公约数，找到后立刻终止循环，这样只会输出一次结果。

修改后的代码：

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;
        int minNum = Math.min(X, X1);
        // 从较小数开始向下遍历
        for(int i = minNum; i >= 1; i--) { 
            if(X % i == 0 && X1 % i == 0) { 
                gcd = i;
                break; // 找到最大公约数后直接退出循环，不用继续找
            }
        }
        System.out.printf("GCD of %d and %d is: %d", X, X1, gcd);  
    }
}

方案2：用欧几里得算法（更高效） #

如果想使用欧几里得算法（辗转相除法）——这是计算最大公约数的标准高效方法，代码实现如下：

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 num1 = input.nextInt();
        int num2 = input.nextInt();
        
        int a = num1;
        int b = num2;
        // 辗转相除核心逻辑
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        System.out.printf("GCD of %d and %d is: %d", num1, num2, a);  
    }
}

额外说明 #

• 原代码的问题在于每次找到公约数就打印，且从小到大遍历，所以会输出所有公约数。从大到小遍历找到第一个就停，是暴力法里效率最高的方式。
• 欧几里得算法的时间复杂度远低于暴力枚举，处理大数时优势特别明显。

内容的提问来源于stack exchange，提问作者Conner Diers