1. 定义法

package GCD;
import java.util.Scanner;
//定义法，根据最大公约数的定义进行求解
public class Definition {
    public static void main(String[] args) {
        System.out.println("请输入两个非零整数：");
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println("这两个整数的最大公约数为："+ definition(a,b));
    }
    public static int definition(int num1, int num2) {
        int res;
        if (num1 > num2)
            res = num2;
        else
            res = num1;
        while(true) {
            if (num1%res == 0 && num2%res == 0)
                break;
            else
                res = res - 1;
        }
        return res;
    }
}

2. 欧几里得算法

package GCD;
import java.util.Scanner;
//欧几里得算法，又称辗转相除法
public class Euclid {
    public static void main(String[] args) {
        System.out.println("请输入两个非零整数：");
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println("这两个整数的最大公约数为："+ euclid(a,b));
    }
    public static int euclid(int inte1, int inte2) {
        int surplus ;
        surplus  = inte1%inte2;
        while(surplus  != 0) {
            inte1 = inte2;
            inte2 = surplus ;
            surplus  = inte1%inte2;
        }
        return inte2;
    }
}

3. 辗转相减法

package GCD;
import java.util.Scanner;
//辗转相减法
public class Subtraction {
    public static void main(String[] args) {
        System.out.println("请输入两个非零整数：");
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println("这两个整数的最大公约数为："+subtraction(a,b));
    }
    public static int subtraction (int num1, int num2) {
        while(true) {
            if (num1 > num2)
                num1 -= num2;
            else if (num1 < num2)
                num2 -= num1;
            else
                return num1;
        }
    }
}

4. 分解质因子法

package GCD;
import java.util.ArrayList;
import java.util.Scanner;
//质因数分解法，将两个数的所有质因子分解出来，然后将公共的因子相乘，得到的就是最大公约数。
public class Prime {
    public static void main(String[] args) {
        System.out.println("请输入两个非零整数：");
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println("这两个整数的最大公约数为："+ getGCD(a,b));
    }
    public static ArrayList<Integer> getPrimeFactors(int num) {
        // 初始化质因子序列
        ArrayList<Integer> factorList = new ArrayList();
        // 循环迭代求质因子
        int i = 2;
        while (i <= num) {
            if (num % i == 0) {
                factorList.add(i);
                num /= i;
            } else {
                i++;
            }
        }
        return factorList;
    }
    public static int getGCD(int num1, int num2) {
        // 先获得绝对值，保证负数也可以求
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        // 获得两个数的质因子序列
        ArrayList<Integer> factors1 = getPrimeFactors(num1);
        ArrayList<Integer> factors2 = getPrimeFactors(num2);
        // 设初始最大公约数为 1
        int gcd = 1;
        // 返回从开头找公共的质因子，相乘起来
        for (int i = 0; i < factors1.size(); i++) {
            for (int j = 0; j < factors2.size(); j++) {
                if (factors1.get(i) == factors2.get(j)) {
                    // 将公共的质因子累乘
                    gcd *= factors1.get(i);
                    // num2 的质因子序列除去找到的，减少第二次重复找
                    factors2.remove(j);
                    // 退出第二重循环, 一次只找一对公共的质因子
                    j = factors2.size();
                }
            }
        }
        return gcd;
    }
}