Java中获取数量的最快因素的最快方法是什么

Question

我正在尝试用Java编写一个函数,它将返回特定数字所具有的因子数.

应考虑以下限制.

1. 它应该用BigInteger完成
2. 存储先前生成的数字是不允许的,因此更多的处理和较少的内存.(不能使用"阿特金筛"像这样)
3. 负数可以忽略.

这是我到目前为止所做的,但它非常慢.

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;
}

Answer 1

我可以提出更快的解决方案,但我觉得它还不够快.您的解决方案将运行O(n),我的解决方案将运行O(sqrt(n)).

我将使用如下事实:如果n = x _i1 ^p1*x _i2 ^p2*x _i3 ^p3*... x _ik ^pk是素数因子化n(即x _{i j}都是不同的素数)则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,您可能会发现它更适合保留number并使另一个变量等于number迭代.

我认为对于不大于2 ^64的数字,此代码将运行得相当快.

编辑我将合理快速地添加完整性的答案.正如在下面的评论中可以看到的,我对Betlista提出的测试用例100000007 ^2的算法的性能进行了几次测量:

• 如果使用算法,我的机器上所花费的时间是57秒.
• 如果我只考虑奇数,则时间减少到28秒
• 如果我将结束条件的检查更改为while与number使用二进制搜索找到的平方根进行比较,则所花费的时间减少到22秒.
• 最后,当我尝试切换所有BigIntegers时long,时间减少到2秒.由于所提出的算法运行速度不够快,因此number大于该范围long可能有意义地将实现切换到long