欧几里得算法

欧几里得算法（英语：Euclidean algorithm），又称 辗转相除法，是求最大公约数的算法。它是已知最古老的算法， 其可追溯至公元前300年前。

// 求出两个正整数的最大公约数
public class MethodOfSuccessiveDivision {
    public static void main(String[] args) {
        System.out.println(gcd(1071, 462));
    }
    public static int gcd(int a, int b){
        if(b == 0){
            return a;
        }else{
            return gcd(b, a % b );
        }
    }
}

基本原理

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，即gcd(a,b)=gcd(b,a mod b) 。

最大公约数：最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。例如：18 与 12 的最大公约数为 6 。

短除法

短除法是求最大公因数的一种方法：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。

参考文档

https://www.cxyxiaowu.com/995.html