What is the fastest way in Java to get the amount of factors a number has

Question

I am trying to write a function in Java that will return the number of factors a specific number has. The following restrictions should be taken into account. - It should be done with BigInteger - Storing the previously generated numbers is not allowed, thus more processing and less memory. (You can not use "Sieve of Atkin" like in this) - Negative numbers can be ignored. This is what I have so far, but it is extremely slow. ``` 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; } ```

Accepted Answer

I can propose faster solution, though I have a feeling that it will not be fast enough yet. Your solution runs in `O(n)` and mine will work in `O(sqrt(n))`.

I am going to use the fact that if n = xi1p1 * xi2p2 * xi3p3 * ... xikpk is the prime factorization of `n` (i.e. xij are all distinct primes) then n has (p1 + 1) * (p2 + 1) * ... * (pk + 1) factors in total.

Now here goes the solution:

```
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);
```

This can be further optimized if you consider the case of 2 separately and then have the step for `x` equal to 2 not 1 (iterating only the odd numbers).

Also note that in my code I modify `number`, you might find it more suitable to keep `number` and have another variable equal to `number` to iterate over.

I suppose that this code will run reasonably fast for numbers not greater than 264.

EDIT I will add the measures of reasonably fast to the answer for completeness. As it can be seen in the comments below I made several measurements on the performance of the proposed algorithm for the test case 1000000072, which was proposed by Betlista:

- If the algorithm is used as is the time taken is 57 seconds on my machine.

- If I consider only the odd numbers the time is reduced to 28 seconds

- If I change the check for the end condition of the `while` to comparing with the square root of `number` which I find using binary search the time taken reduces to 22 second.

- Finally when I tried switching all the `BigInteger`s with `long` the time was reduced to 2 seconds. As the proposed algorithm will not run fast enough for `number` larger than the range of `long` it might make sense to switch the implementation to `long`

What is the fastest way in Java to get the amount of factors a number has

Solution

Problem

Related problems