算法 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

代码