判断质数
如果n不是质数，那么在根号n之前一定有一个因数，所以只需要遍历到根号n即可
public boolean isPrime(int n){
if(n<=1) return false;
if(n<=3) return true;
double upperBound = Math.sqrt(n) + 1;
for (int i=2; i<upperBound; i++){
if(n%i == 0) return false;
}
return true;
}
质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。利用这个特性可以进一步优化。
求所有因数
从1到n遍历，能被整除就是因数
public static List<Integer> allFactors(int n){
List<Integer> res = new ArrayList<>();
for(int i=1; i<=n; i++){
if(n%i == 0){
res.add(i);
}
}
return res;
}
最大公因数
直接遍历所有因数，暴力解，可行，但时间复杂度太高。
一般用如下两种解法
辗转相除法
两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
public static int getNum(int a, int b){
int numberA = Math.max(a, b);
int numberB = Math.min(a, b);
return gcd(numberA, numberB);
}
// a是大的，b是小的
public static int gcd(int a, int b){
if(a % b == 0){
return b;
}else{
return gcd(b, a%b);
}
}
当两个整数较大时，取模运算的性能较低
更相减损术
两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
public static int getNum2(int a, int b){
return gcd2(a, b);
}
public static int gcd2(int a, int b){
if(a==b) return a;
int numberA = Math.max(a, b);
int numberB = Math.min(a, b);
return gcd2(numberA-numberB, numberB);
}
虽然单次减法运算比取模运算快很多，但是运算次数大大增加。
两者结合起来，能够在数字比较大时获得更好的性能。
代码略
最小公倍数
利用公式
m * n / 最大公因数 = 最小公倍数
可以用辗转相除法求最大公因数
