作者热门文章
- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
<分区>
我想求出小于 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;
}
首先,上述算法的复杂度是多少??我很难找到它??
此外,对于质数较大的数来说,它会太慢。
有没有更好的算法,或者如何优化这个算法??
我只是写了下面的代码来利用筛法找到大于 2 的某个自然数的最大质因数。 该程序构建、运行并适用于较小的测试值,但对于大于 1000000 的值只会崩溃。 我自己写了这个——并且相信它可能会非常低效——
我是一名优秀的程序员,十分优秀!