最大公约数概念：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;
}
}
