projecteuler-3 质因数除法中的 if vs while 循环

Question

今天我使用 projecteulers 题练习了我的编码测试。在做质因数除法时，我偶然发现了一些我觉得很奇怪的事情。这是相关代码（res 是一个 ArrayList）：

for (int x = 2; x <= n; x++){       
    if (n % x == 0){
        System.out.println("Prime found: " + x);
        res.add(x);
        n = n / x;
    }       
}

其中将 1000 分为 [2, 4, 5, 25]。过了一会儿，我尝试用 while 循环替换 if 语句，它打印出正确答案 [2, 2, 2, 5, 5, 5].

显然有一些我不明白的地方，有人可以给我解释一下吗？

编辑：

较新的代码：

for (int x = 2; x <= n; x++){       
    while (n % x == 0){
        System.out.println("Prime found: " + x);
        res.add(x);
        n = n / x;
    }       
}

Answer 1

区别是：

如果您使用if，每个数字只测试一次。因此，如果您能够取出 2，则只能尝试一次。下一个可以取出的数字是 4，尽管它不是质数。这同样适用于 5 resp。 25.
如果您使用 while，您将测试每个数字，直到您知道它不再在要测试的数字中。

Answer 2

你也可以改成

for (int x = 2 ; x <= n/x ; ) {       
        if (n % x == 0) {
            System.out.println("Prime factor: " + x);
            res.add(x);
            n = n / x;
        }       
        else {
            x++;         // increment moved here
        }
    }
if (n > 1) {
    System.out.println("Prime factor: " + n);
    res.add(n);
}

我还更改了终止条件，以使其在 n 的最大质因数本身很大的情况下更加有效，因为如果 n = a*b 和 a <= b , 然后 a*a <= a*b = n, 即 a <= n/a.

这将重复对质因数的测试，因为正如您所发现的，某些数字具有多个相同大小的质因数（例如 1000 = 2*2*2*5*5*5）。它等同于您的 while 循环，因为增量现在是有条件的，仅在测试候选人不是 n 的因素时执行。

projecteuler-3 质因数除法中的 if vs while 循环

if vs while loop in projecteuler-3 prime factor division

java

if-statement

while-loop

primes

prime-factoring