质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

暴力法

• 介绍：对所有平方根以下的数进行取模操作，如果没有余数即表示可以整除，因此并非质数。

• 实现：

    public static boolean isPrimerForceNew(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
  

埃拉托斯特尼筛法

• 介绍：埃拉托斯特尼筛法: 质数的倍数必定不是质数，因此默认认为所有数都是质数，从小的数开始遍历，如果是质数，那么它的倍数全部设置为非质数。

  根据筛法的特点，再进行优化：

  1. 由于初始化布尔数组时默认值为 false，因此默认认为 false 表示是质数，true 表示非质数，因此将布尔数组命名为：isNotPrimer。

  2. 质数 2 的倍数必定不是质数，因此对于 2 以为的所有偶数，一律判定为非质数。

  3. 由于 2 的倍数都判定为非质数，因此遍历操作直接对奇数操作即可。

• 实现：

    public static boolean sieveOfEratosthenes(int num) {
        if (num < 2)        return false;
        if (num == 2)       return true;
        if ((num & 1) == 0) return false;
        boolean[] isNotPrimer = new boolean[(int) Math.sqrt(num) + 1];
        for (int i = 3; i < isNotPrimer.length; i += 2) {
            if (!isNotPrimer[i]) {
                for (int j = 3; i * j < isNotPrimer.length; j += 2) {
                    isNotPrimer[i * j] = false;
                }
            }
        }
        for (int i = 3; i < isNotPrimer.length; i += 2) {
            if (!isNotPrimer[i]) {
                if (num % i == 0) return false;
            }
        }
        return true;
    }
  

• 分析：典型的牺牲空间换取时间的操作，对于超大数组根本无法操作，因为操作系统不允许申请如此之大的数组。

分解质因数

• 介绍：每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

  分解质因数这个操作只针对合数，因此所有自然数里的质数返回结果都是空的。

  由于是分解成质因数，同样是对于质数的判定与操作，同时由于涉及到质数的保存操作，因此采用筛法求质数是非常契合的。

• 实现：

    public static int[] primerFactor(int num) {
        int x = num;
        if (x < 4) return new int[0];
        List<Integer> tmpRes = new ArrayList<>();
        /* 将合数从偶数转化为奇数，避免下文过多对于 2 的计算 */
        while ((x & 1) == 0) {
            tmpRes.add(2);
            x /= 2;
        }
        /* 筛法求质数表 */
        boolean[] isNotPrimer = new boolean[(int) Math.sqrt(x) + 1];
        for (int i = 3; i < isNotPrimer.length; i += 2) {
            if (isNotPrimer[i]) continue;
            for (int j = 3; i * j < isNotPrimer.length; j += 2) {
                isNotPrimer[i * j] = false;
            }
        }
        /* 判断质数公因数 */
        for (int i = 3; i < isNotPrimer.length; i += 2) {
            if (isNotPrimer[i] || x % i != 0) continue;
            tmpRes.add(i);
            x /= i;
            i -= 2;
        }
        /* 如果已经开过公因数了，那么最终剩下的也是公因数 */
        if (x != num && x != 1) tmpRes.add(x);
        int[] res = new int[tmpRes.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = tmpRes.get(i);
        }
        return res;
    }
  

最大公约数

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

辗转相除法（欧几里得算法）

• 介绍：以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

  由于公约数必定能使二者整除，因此利用彼此除法取余的操作，从大到小慢慢取余数出来，直至余数是公因数，此时就是最大公因数了。

• 实现：

    public static int euclideanAlgorithm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        int max = Math.max(Math.abs(a), Math.abs(b)), min = Math.min(Math.abs(a), Math.abs(b));
        if (max % min == 0) return min;
        return euclideanAlgorithm(min, max % min);
    }
  

更相减损法

• 介绍：如果二者是偶数，都除二；若否，则大的数减小的数，如果减数和差相同，则减数（差）为二奇数的最大公约数，将二奇数的最大公约数进行若干次乘二操作（和最开始除二的次数）即是最大公约数。

• 实现：

    public static int decreasesTechnique(int a, int b) {
        if (a == 0 || b == 0) return 0;
        int max = Math.max(Math.abs(a), Math.abs(b)), min = Math.min(Math.abs(a), Math.abs(b));
        if ((max & 1) == 0 && (min & 1) == 0) return 2 * decreasesTechnique(max >> 1, min >> 1);
        if (max == min || max - min == min) return min;
        return decreasesTechnique(max - min, min);
    }
  

• 分析：公因数最直观的操作在于乘（除）法操作上，因此辗转相除法较更相减损法更易于理解，同时乘除操作的计算次数也要比加减操作快很多。

质因数分解法

• 介绍：对二者都进行分解质因数的操作，将二者相同的质因数相乘，即为最大的公因数

• 实现：

    public static int samePrimerFactor(int a, int b) {
        if (a == 0 || b == 0) return 0;
        int max = Math.max(Math.abs(a), Math.abs(b)), min = Math.min(Math.abs(a), Math.abs(b));
        if (max % min == 0) return min;
        int[] samePrimerFactors = DoubleArray.sameInTwoSortedArrays(PrimerNumber.primerFactor(max), PrimerNumber.primerFactor(min));
        int res = 1;
        for (int i : samePrimerFactors) {
            res *= i;
        }
        return res;
    }
  

• API：

  方法名	描述
  sameInTwoSortedArrays	获取两个已排序数组中的相同元素
  primerFactor	分解一个合数，返回质因数数组

• 分析： 较为繁琐，不过是最为直观的解法，可以理解为求最大公因数的暴力解法，虽然步骤有点冗长🤣