为什么我们在获取质因数时不必检查数字是否为质数？
Why we dont have to check if the number is prime when getting prime factors?
这是寻找质因数的典型代码：
public static List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}
我的问题是为什么我们在将它添加到列表之前不检查它是否是质数？
我们可以通过反证法证明那不可能发生。
假设某个合数被添加到列表中。必须有一些 smallest 合数被添加到列表中。我们称它为c，并想象它的最小质因数是p。我们知道 p < c，所以循环必须有 运行 with p 在它之前 运行 with c。当循环对 p 执行 运行 时，我们知道循环会找到 p 作为数字 n 的约数，因为 p 是 c 的约数，而 c 是 n 的约数。但在这样做之后，代码将通过划分 p 的所有副本来更新 n。这意味着当我们到达循环 运行 数字 c 的部分时，数字 c 不会再整除 n 因为 p 整除 c，但 p 不会整除 n 的这个新值（记住，我们把 p) 的所有副本都分了出来。因此，c 不会被添加到列表中 - 自相矛盾！
在这里我们不需要检查天气数字是否是质数，因为
要添加的数字肯定是素数..让我们举个例子
1)16 是 2,4,8,16 的倍数，但由于 while 循环只加了 2
2)18 它的倍数是 2,3,6,9 和 18 但是因为 while 循环只加了 2 和 3 ,3
3) n 一个整数
我们不知道它的倍数但是
当 i=2 时，数字变为奇数，所以现在所有偶数都被消除（意味着任何二的倍数都不能被 n/2 整除）
when i=3 if mod is zero then add and all the multiple get eliminate
（表示任何 3 的倍数都不能被 n/3 整除）
这就是我们计算数字是否为素数的方式，例如将数字除以 2 然后它也不是 4、6、8 等的倍数
在排序中，我们通过除以小数字来消除除 之外的其他数字
我希望你能理解其中的逻辑
这是寻找质因数的典型代码：
public static List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}
我的问题是为什么我们在将它添加到列表之前不检查它是否是质数？
我们可以通过反证法证明那不可能发生。
假设某个合数被添加到列表中。必须有一些 smallest 合数被添加到列表中。我们称它为c，并想象它的最小质因数是p。我们知道 p < c，所以循环必须有 运行 with p 在它之前 运行 with c。当循环对 p 执行 运行 时，我们知道循环会找到 p 作为数字 n 的约数，因为 p 是 c 的约数，而 c 是 n 的约数。但在这样做之后，代码将通过划分 p 的所有副本来更新 n。这意味着当我们到达循环 运行 数字 c 的部分时，数字 c 不会再整除 n 因为 p 整除 c，但 p 不会整除 n 的这个新值（记住，我们把 p) 的所有副本都分了出来。因此，c 不会被添加到列表中 - 自相矛盾！
在这里我们不需要检查天气数字是否是质数，因为 要添加的数字肯定是素数..让我们举个例子
1)16 是 2,4,8,16 的倍数，但由于 while 循环只加了 2
2)18 它的倍数是 2,3,6,9 和 18 但是因为 while 循环只加了 2 和 3 ,3
3) n 一个整数 我们不知道它的倍数但是 当 i=2 时，数字变为奇数，所以现在所有偶数都被消除（意味着任何二的倍数都不能被 n/2 整除）
when i=3 if mod is zero then add and all the multiple get eliminate （表示任何 3 的倍数都不能被 n/3 整除）
这就是我们计算数字是否为素数的方式，例如将数字除以 2 然后它也不是 4、6、8 等的倍数
在排序中，我们通过除以小数字来消除除 之外的其他数字
我希望你能理解其中的逻辑