java - 在 Java 中获取一个数字的因子数量的最快方法是什么

Question

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

应考虑以下限制。

1. 应该用 BigInteger 来完成
2. 不允许存储以前生成的数字，因此需要更多的处理和更少的内存。(您不能像 this 中那样使用“阿特金筛法”)
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_ij 都是不同的素数)那么 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⁶⁴ 的数字运行速度相当快。

编辑 为了完整性，我会在答案中添加相当快的措施。从下面的评论中可以看出，我对 Betlista 提出的测试用例 100000007² 所提出算法的性能进行了多项测量:

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