java - 大数的质因数分解

<分区>

我想求出小于 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) .

关于java - 大数的质因数分解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12251962/