java - 大量的素数分解

Closed. This question is off-topic。它当前不接受答案。












想改善这个问题吗？ Update the question，所以它是用于堆栈溢出的on-topic。

7年前关闭。



Improve this question




我想找到小于10 ^ 12的大数的质分解。
我得到了以下代码(在Java中):

public static List<Long> primeFactors(long numbers) {
        long n = numbers;
        List<Long> factors = new ArrayList<Long>();
        for (long i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

首先，上述算法的复杂度是多少？我很难找到它。

而且对于大量的素数来说太慢了。

是否有更好的算法，否则如何优化该算法？

最佳答案

如果您想分解许多大数，那么最好先找到sqrt(n)之前的质数(例如使用Sieve of Eratosthenes)。然后，您只需要检查那些质数是否是因数，而不必测试所有i <= sqrt(n)。