我试图找到数字 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]
}
}
最佳答案
如果您尝试分解的数字是两个大素数的乘积,则分解的计算成本很高。但是,您的算法(正如您所观察到的)效率特别低。
您的算法称为试除法,正如您所编写的那样,它的复杂度为 O(N)。它可以很容易地改进为最坏情况 O(N0.5) 算法;见下文。
维基百科页面总结了许多不同难度的更好算法:请参阅 https://en.wikipedia.org/wiki/Integer_factorization .
分解任意非质数的问题已知属于 NP 问题,但怀疑不属于 P 问题:参见 https://en.wikipedia.org/wiki/NP_(complexity)#Formal_definition .
以下是一些加快程序速度的简单方法:
不要使用
Long
进行计算。请改用long
。您的代码将生成并垃圾收集大量Long
对象。当使用试除法对数字
n
进行因式分解时,当您到达sqrt(n)
时,您可以停止寻找质因数。找到质因数后,您可以通过将原始数字除以该因式,然后尝试对结果进行因式分解来加速因式分解。 (事实上,您已经在这样做了。)
(但与更复杂的算法相比,这只是“鸡饲料”。)
关于java - 查找数字 600851475143 的最大质因数的更有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50156716/