如何在 java 中优化此代码？

Question

public class factorize {

public static void f(int n) {
    int i = 2;
    while( n > 1) {
        if (n%i == 0) {
            System.out.println("Factors " + i);
            n = n / i;
        }
        else {
            i++;
        }
    }
}

你好，我在java做一个factorize的函数，但是执行了很多次，网上找了一些定理，结果都是一样的。你能告诉我一些算法来尽可能快地执行这个因式分解吗？此代码大约需要 2 分钟。

Answer 1

试试这个：

public static void f(int n) {
    int i = 2;
    while(i*i <= n) {
        if (n%i == 0) {
            System.out.println("Factors " + i);
            n = n / i;
        }
        else {
            i++;
        }
    }

    if (n > 1) {
        System.out.println("Factors " + n);
    }
}

之所以可行，是因为您只能有一个大于 sqrt(n) 的质因数：如果您有两个，它们的乘积将超过 n，因为 sqrt(n)*sqrt(n) = n。所以检查这些就足够了，然后如果 n > 1，剩下的 n 是另一个素数。

注意： 2732983441203969650 是一个很大的数字，不适合 int。如果您希望您的算法适用于它，您应该考虑使用 long。请注意，它的平方根也非常大，因此算法可能仍然很慢。对于如此大的数字，因式分解非常困难。您可以尝试的一种算法可能会在合适的时间内对 64 位数字起作用，它是 Pollard's Rho algorithm.

您可以在代码中优化的其他内容：

单独检查2，然后只检查被奇数整除；
使用 Sieve of Eratosthenes 生成小于 n 平方根的素数，并检查这些素数的整除性。

如何在 java 中优化此代码？

How to optimize this code in java?

java

algorithm

math

optimization