java - 查找数字 600851475143 的最大质因数的更有效方法

Question

我试图找到数字 600851475143 的最大质因数，并通过下面的代码成功，但我知道这是一种残酷的方式，可能有更有效和优雅的方法来解决这个问题。但是，我无法立即想到任何问题，希望有人可以分享他们的解决方案并进行解释。

public class Solution {

    // find prime numbers
    ArrayList<Long> primelist = new ArrayList<>();

    ArrayList<Long> findPrime(Long num) {
        for (Long i = Long.valueOf(2); i <= num; i++) {
            if (num % i == 0) {
                primelist.add(i);
                num = num / i;
                if (num == 1) {
                    break;
                }
            }
        }
        System.out.println(primelist);
        return primelist;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.findPrime(Long.valueOf(600851475143L)); // [71, 839, 1471, 6857]
    }
}

Answer 1

如果您尝试分解的数字是两个大素数的乘积，则分解的计算成本很高。但是，您的算法(正如您所观察到的)效率特别低。

• 您的算法称为试除法，正如您所编写的那样，它的复杂度为 O(N)。它可以很容易地改进为最坏情况 O(N^0.5) 算法；见下文。

• 维基百科页面总结了许多不同难度的更好算法:请参阅 https://en.wikipedia.org/wiki/Integer_factorization .

• 分解任意非质数的问题已知属于 NP 问题，但怀疑不属于 P 问题:参见 https://en.wikipedia.org/wiki/NP_(complexity)#Formal_definition .

<小时/>

以下是一些加快程序速度的简单方法:

1. 不要使用Long进行计算。请改用long。您的代码将生成并垃圾收集大量 Long 对象。

2. 当使用试除法对数字 n 进行因式分解时，当您到达 sqrt(n) 时，您可以停止寻找质因数。

3. 找到质因数后，您可以通过将原始数字除以该因式，然后尝试对结果进行因式分解来加速因式分解。 (事实上​​，您已经在这样做了。)

(但与更复杂的算法相比，这只是“鸡饲料”。)