我试图在
Java中编写一个函数,它将返回特定数字的因子数.
应考虑以下限制.
>应该用BigInteger完成
>不允许存储以前生成的数字,因此更多的处理和更少的内存(您不能像this那样使用“Sieve of Atkin”)
>负数可以忽略.
这是我到目前为止,但这是非常缓慢的.
public static int getNumberOfFactors(BigInteger number) {
// If the number is 1
int numberOfFactors = 1;
if (number.compareTo(BigInteger.ONE) <= 0) {
return numberOfFactors;
}
BigInteger boundry = number.divide(new BigInteger("2"));
BigInteger counter = new BigInteger("2");
while (counter.compareTo(boundry) <= 0) {
if (number.mod(counter).compareTo(BigInteger.ZERO) == 0) {
numberOfFactors++;
}
counter = counter.add(BigInteger.ONE);
}
// For the number it self
numberOfFactors++;
return numberOfFactors;
}
解决方法
我可以提出更快的解决方案,虽然我有一种感觉,它还不够快.你的解决方案运行在O(n),我的工作在O(sqrt(n)).
我将使用如下事实：如果n = xi1p1 * xi2p2 * xi3p3 * … xikpk是n的素因子分解(即xij都是不同的素数),那么n具有(p1 1)*(p2 1)* .. *(pk 1)因素.
现在这里解决方案：
BigInteger x = new BigInteger("2");
long totalFactors = 1;
while (x.multiply(x).compareTo(number) <= 0) {
int power = 0;
while (number.mod(x).equals(BigInteger.ZERO)) {
power++;
number = number.divide(x);
}
totalFactors *= (power + 1);
x = x.add(BigInteger.ONE);
}
if (!number.equals(BigInteger.ONE)) {
totalFactors *= 2;
}
System.out.println("The total number of factors is: " + totalFactors);
如果您分别考虑2的情况,然后让x等于2的步骤不为1(仅迭代奇数),则可以进一步优化.
另请注意,在我的代码中我修改号码,你可能会发现它更适合保留数字,并有另一个变量等于number来迭代.
我想这个代码对于不大于264的数字将会合理运行.
编辑我将把相应的措施加快到答案的完整性.从下面的评论可以看出,我对Betlista提出的测试案例1000000072的算法性能进行了几次测试：
>如果使用算法,我的机器上所用的时间为57秒.>如果我只考虑奇数,时间缩短到28秒>如果我更改对于结束条件的检查,以便与使用二进制搜索找到的数字的平方根进行比较,则所花费的时间减少到22秒.>最后,当我尝试将所有BigIntegers全部切换到时间缩短到2秒时.由于所提出的算法对于长于long的范围的运行速度不够快,所以将实现切换到很长时间是有意义的
