最大公约数概念：https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import static java.util.stream.Collectors.toList;

/**
 * @Author Noperx
 * @Create 2021-07-09 20:10
 */
public class GCD {
    /**
     * 最大公约数求法：更相减损法
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd(int a,int b){
        while (a/2==0 && b/2==0){
            a = a/2;
            b = b/2;
        }

        while (!(a==b)){
            if (a>b){
                a -= b;
            }else{
                b -= a;
            }
        }
        return a;
    }

    /**
     * 辗转相除法(欧几里德算法)
     * 用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。
     * 最后所得的那个最大公约数，就是所有这些数的最大公约数。
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd2(int a,int b){
        int result = 0;
        while(b != 0){
            result = a % b;
            a = b;
            b = result;
        }
        return a;
    }

    /**
     * 分解质因数
     *
     * @param a
     * @return
     */
    public static List<Integer> getFactor(int a){
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= a; i++) {
            while (a % i == 0) {
                list.add(i);
                a = a / i;
            }
        }
        return list;
    }

}