算法 day1
最小公倍数&最大公约数
结论1： 如果两个整数互为质数，那么这两个数的最小公倍数就是它们的乘积,最大公约数是1
结论2： 最小公倍数 = 两整数之积 / 最大公约数
为了避免出现混淆，说明下容易得出错误推导：
其中一个数除以两者的最大公约数的值与另一个数互为质数，因此最小公倍数就是两数之积除以最大公约数。
上述错误推导举例： 12和9， 9除以3，得到3， 3与12不是互为质数，但最小公倍数是36，因为从另一个角度上，12除以3得到4，4与9互为质数。
正确的是：
两个数同时除以最大公约数得到的商两者互为质数。 互为质数，其中可能包含合数。例如 12和9最大公约数是3，得到的是 4 和 3,两者互为质数，但4不是质数。
题型
输入整数A和B,输出这两个整数的最大公约数和最小公倍数（由于两整数相乘除以最大公约数即可得到，因此本题只考虑最大公约数）。
边界问题
如果有输入0，我们认为无效输入。
解法一 穷举法
思路：一般思路从2开始穷举数字，直到穷举到较小的那个数（更准确的说是绝对值更小）为止。考虑到我们求的是最大公约数，那么可以反过来穷举，这样相比原有思路更快。
``
public static int findGCD(int a, int b){
if(a == 0 || b == 0){
throw new IllegalArgumentException("a="+a + "and b="+b+" is invalid");
}
a = Math.abs(a);
b = Math.abs(b);
int min = Math.min(a,b);
int gcd = min;
while(gcd > 1){
if(a % gcd == 0 && b % gcd == 0){
return gcd;
}
gcd --;
}
return gcd;
}
``
解法二 质因数分解法
思路：把两个整数进行质因数分解，然后从中找出最大的公共因数，即最大公约数。
public static int findGCD2(int a, int b){
if(a == 0 || b == 0){
throw new IllegalArgumentException("a="+a + "and b="+b+" is invalid");
}
a = Math.abs(a);
b = Math.abs(b);
List<Integer> first = getPrimeFactors(a);
List<Integer> second = getPrimeFactors(b);
//找到公共因数，例如
//36和 9
// 36 = 2 * 2 * 3 * 3
// 9 = 3 * 3
//公共部分是 3 * 3，因此最大公约数是9
//因此每找到一个，累积该因数，并且两个集合同时排除该因数
int gcd = 1;
int tmpJ = 0;
for (int i = 0; i < first.size(); i++) {
for (int j = tmpJ; j < second.size(); j++) {
if(first.get(i) == second.get(j)){
gcd *= first.get(i);
//由于外层的循环往后会直接排除前面的因数，因此只需要移除后一个集合
second.remove(j);
//由于我们因数是从小到大排列的，因此后续从此位置开始找开始找
tmpJ = j;
break;
}
}
}
return gcd;
}
//拆分质因数，因数是从小到大插入有序集合中
private static List<Integer> getPrimeFactors(int target){
List<Integer> factors = new ArrayList<>();
int factor = 2;
while(factor <= target){
if(target % factor == 0){
factors.add(factor);
target /= factor;//去除该因数
factor = 2;//重新从2开始计算。
}else{
factor ++;
}
}
return factors;
}
解法三 辗转相除法
思路：欧几里得算法 gcd(a,b) = gcd(b, a mod b) 效率最高
public static int findGCD3(int a, int b){
if(a == 0 || b == 0){
throw new IllegalArgumentException("a="+a + "and b="+b+" is invalid");
}
a = Math.abs(a);
b = Math.abs(b);
int min = Math.min(a,b);
int max = Math.max(a,b);
int mod;
while(true){
mod = max % min;
if(mod == 0){
return min;
}
max = min;
min = mod;
}
}
Codes
代码
