质数
质数是指在大于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; }
埃拉托斯特尼筛法
-
介绍:埃拉托斯特尼筛法: 质数的倍数必定不是质数,因此默认认为所有数都是质数,从小的数开始遍历,如果是质数,那么它的倍数全部设置为非质数。
根据筛法的特点,再进行优化:
-
由于初始化布尔数组时默认值为 false,因此默认认为 false 表示是质数,true 表示非质数,因此将布尔数组命名为:
isNotPrimer
。 -
质数 2 的倍数必定不是质数,因此对于 2 以为的所有偶数,一律判定为非质数。
-
由于 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
分解一个合数,返回质因数数组 -
分析: 较为繁琐,不过是最为直观的解法,可以理解为求最大公因数的暴力解法,虽然步骤有点冗长🤣