第一种（暴力法）

思路：取a、b两个数，再取一个变量i，变量i的初始值为1，从1开始遍历到a和b中小的那个数，每一次i递增的时候都用a和b除以i，找到最后能够同时整除那个数，就是最大公约数。

代码

import java.util.Scanner;

/**
 * @Param a,b :求它们两个的最大公约数  gcd :最大公约数值
 * @Author 小李同学
 * @Date 2021/1/20 20:42
 * @return 无
 * @description 最大公约数:暴力解法
 */
public class test1 {
    public static void main(String[] args) {

        //第一种：暴力解决
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int gcd = 1;
        for (int i = 2; i <= (a > b ? b : a); i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }
        System.out.println("最大公约数为：" + gcd);
    }
}

第二种（短除法）

思路：把a和b分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是最大公约数。

例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，12就是24和60的最大公约数。

代码

import java.util.Scanner;

/**
 * @Param a,b :求它们两个的最大公约数  gcd :最大公约数值
 * @Author 小李同学
 * @Date 2021/1/20 20:56
 * @return 无
 * @description 最大公约数：短除法
 */
public class test2 {
    public static void main(String[] args) {

        //第二种：短除法
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int gcd = 1;
        for (int i = 2; i <= (a > b ? b : a); i++) {
            while (a % i == 0 && b % i == 0) {
                gcd = gcd * i;
                a = a / i;
                b = b / i;
            }
        }
        System.out.println("最大公约数为：" + gcd);
    }
}

第三种（辗转相除法递归）

思路：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止，最后的除数就是这两个数的最大公约数。

代码

import java.util.Scanner;

/**
 * @Param a,b :求它们两个的最大公约数  gcd :最大公约数值
 * @Author 小李同学
 * @Date 2021/1/20 21:03
 * @return gcd(a,b) :int
 * @description 最大公约数：辗转相除法(递归)
 */
public class test3 {
    public static void main(String[] args) {

        //第三种：辗转相除法(递归)
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int gcd = gcd(a, b);
        System.out.println("最大公约数为：" + gcd);
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            int c = b;
            b = a % b;
            a = c;
            return gcd(a,b);
        }
    }
}

第四种（辗转相除法非递归）

代码

import java.util.Scanner;

/**
 * @Param a,b :求它们两个的最大公约数  gcd :最大公约数值
 * @Author 小李同学
 * @Date 2021/1/20 21:16
 * @return 无
 * @description 最大公约数：辗转相除法(非递归)
 */
public class test4 {
    public static void main(String[] args) {

        //第四种：辗转相除法(非递归)
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = 1;
        while (b != 0) {
            c = b;
            b = a % b;
            a = c;
        }
        System.out.println("最大公约数：" + a);
    }
}