Java 中的素因数分解代码有什么问题？

Question

我正在尝试创建一种方法来对数字进行质因数分解，它可能不是最有效的，但我不明白为什么它不起作用。

public static ArrayList<Integer> primeFactorize(int num) {
    ArrayList<Integer> primeFactors = new ArrayList<Integer>();

    for (int i = 2; i < Math.sqrt((double) num); i++) {
        if (isPrime(i) && factor(num).contains(i)) {
            primeFactors.add(i);
            num /= i;

            if (isPrime(num)) {
                primeFactors.add(num);
                break;
            }
            i = 2;
        }
    }
    return primeFactors;
}

它调用了我编写的另外两个名为 factor() 和 isPrime() 的方法，它们完全符合您的期望（returns 和 ArrayList 的因素true 或 false 分别取决于输入是否为素数）。

我通过调试器将 num 设置为 12，它在第一个循环中运行良好，它向 primeFactors 添加了 2。但是，当它再次到达数组的顶部时，num 为 6，i 为 2，它退出循环，就好像 i < Math.sqrt((double) num) 返回了 false。

但这没有意义，因为 6 的平方根有点大于 2。我也试过 (double) i < Math.sqrt((double) num)，但它只是做同样的事情。

谁能看到我遗漏了什么？感谢您的任何回复。

编辑：这是我的代码，感谢您的帮助！我确信我可以让它更有效率，所以我可能会稍后再做，但现在这是完美的。

public static ArrayList<Integer> primeFactorize(int num) {
    ArrayList<Integer> primeFactors = new ArrayList<Integer>();

    int i = 2;
    while (i < Math.sqrt((double) num)) {
        if (isPrime(i) && num % i == 0) {
            primeFactors.add(i);
            num /= i;

            if (isPrime(num)) {
                primeFactors.add(num);
                break;
            }
            i = 2;
        }
        else
            i++;
    }
    return primeFactors;
}

Answer 1

在您的 for 循环中，i++ 部分将在每个循环结束时被调用。所以在你的代码中，你设置 i 等于 2。然后，循环结束，将 1 添加到 i，使它成为 3。然后进行比较，3 大于 sqrt(6 ), 所以循环退出。

如果你希望i在下一次迭代中为2，你需要将其设置为一个值，以便在增量操作运行后它将是2 ，而不是之前；在这种情况下，您应该将其设置为 1。更好的解决方案是更改您的代码结构，因此没有必要。，一个while循环会让你决定是否递增，会避免这个问题。

Answer 2

既然你已经接受了答案，我认为你的问题已经解决了。我想指出的是，如果有其他方法，将整数转换为双精度数通常不是一个好主意。因此，我想向您展示下面的实现，它不使用浮点运算。另外我认为检查 num 是否是素数是个坏主意，因为这会减慢算法速度。此外，如果 num % i == 0 的计算结果为真，则 i 始终是质数，因此 isPrime(i) 检查是多余的，并且还会减慢您的算法。

List <Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    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 ;
}

Java 中的素因数分解代码有什么问题？

What is wrong with this prime factorization code in Java?

java

math

primes