11

我正在尝试用 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;
}
4

3 回答 3

17

我可以提出更快的解决方案，尽管我觉得它还不够快。您的解决方案运行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
于 2012-04-13T11:10:34.573 回答
1

一些改进：

  1. 您只需要检查到 sqrt(n)，而不是 n/2。这使得你的算法 O(sqrt(n)) 而不是 O(n)。
  2. 您只需要在检查 2 后检查奇数，这应该会加倍速度。
  3. 虽然你不能使用以前的数字，但你可以构造一个已知素数和少量存储的筛子：2、3 是素数，所以只需要检查（例如）11、13、17、19、23 而不是 12， 14,15,16,18。因此，您可以存储 3 的增量模式：[+2,+4]，每 6 次重复：
var deltas = [2,4];
var period = 6;
var val = 3;
var i=0;
while(val<sqrt(n)) {
    var idx = i%deltas.length; // i modulo num deltas
    val += deltas[idx];
    count += isFactor(n,val);
    // if reached end of deltas, add period
    if(idx == deltas.length-1) {
        val += period - deltas[idx];
    }
    ++i;
}

一旦你得到这个结果，如果它们是因子，你显然必须添加 2 和/或 3。

当我在学校无聊的时候，我把上面的模式弄出来了。您可以计算出任何素数列表的模式，但有一个收益递减规律；您添加的每个素数都会增加周期，并大大增加增量列表的长度。因此，对于一长串已知素数，您会得到一个非常长的增量列表，并且速度只有很小的提高。但是，请测试加速是否值得。

由于它只是剔除已知分数的一部分（使用所示的 2 值增量的 2/3rds），这仍然是 O(sqrt(n))。

将筛子与 sqrt 界限相结合，您应该得到 4/(3*sqrt(n)) 的加速。

[编辑：将句点添加到最后一个值，而不是句点-lastdelta。谢谢@Betlista]

于 2012-04-13T11:58:24.443 回答
0

Boris Strandjev 提出的最快解决方案存在一些问题，即在 Java 中生成大量输出。它是在 Java 中查找非常大整数的除数的最快算法。

这是我将成功运行的代码：

import java.math.BigInteger;
import java.util.Scanner;

class ProductDivisors {

    public static BigInteger modulo=new BigInteger("1000000007");
    public static BigInteger solve=new BigInteger("1");
    public static BigInteger two=new BigInteger("2");
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        BigInteger prod=new BigInteger("1");
        while(N-->0){
            prod=sc.nextBigInteger();
            solve=solve.multiply(prod);
        }
        BigInteger x = new BigInteger("2");
        BigInteger total = new BigInteger("0");
        BigInteger totalFactors =new BigInteger("1");
        while (x.multiply(x).compareTo(solve) <= 0) {
            int power = 0;
            while (solve.mod(x).equals(BigInteger.ZERO)) {
                power++;
                solve = solve.divide(x);
            }
            total = new BigInteger(""+(power + 1));
            totalFactors=totalFactors.multiply(total);
            x = x.add(BigInteger.ONE);
        }
        if (!(solve.equals(BigInteger.ONE))) {
            totalFactors =totalFactors.multiply(two);
        }
        totalFactors=totalFactors.mod(modulo);
        System.out.println(totalFactors);
    }

}

此代码通常将数字数组作为输入，从而相乘将产生大量数字。并且，计算除数的主要代码（包括这里的除数）并给出输出。

我希望这是一种有效的方法，并在需要时提出任何错误或补充。

于 2016-06-05T13:05:35.390 回答