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.

1. It should be done with BigInteger
2. Storing the previous generated numbers are not allowed, thus more processing and less memory.(You can not use "Sieve of Atkin" like in this)
3. 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;
}

Answer 1

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 = x_i1^p1 * x_i2^p2 * x_i3^p3 * ... x_ik^pk is the prime factorization of n (i.e. x_ij 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 2⁶⁴.

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 100000007², 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 BigIntegers 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

Answer 2

Some improvements:

1. You only need to check up to sqrt(n), not n/2. That makes your algorithm O(sqrt(n)) instead of O(n).
2. You only need to check odd numbers after checking 2, which should double the speed.
3. Although you can't use previous numbers, you can construct a sieve with known primes and a little storage: 2, 3 are prime, so only need to check (for example) 11,13,17,19,23 and not 12,14,15,16,18. Thus you can store a pattern of deltas from 3: [+2,+4], repeat every 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;
}

Once you have this result, you obviously have to add 2 and/or 3 if they are factors.

I worked the above pattern out when I was bored at school. You can work out the pattern for any list of primes, but there is a law of diminishing returns; each prime you add increases the period, and hugely increases the length of the list of deltas. So for a long list of known primes, you get an extremely long list of deltas and only a minor improvement in speed. However, do test whether a speed up is worth it.

Since it merely knocks out a known fraction of the values (2/3rds using the 2-value delta shown), this is stil O(sqrt(n)).

Combining the sieve with the sqrt bound, you should get a speedup of 4/(3*sqrt(n)).

[Edit: was adding the period to the last value, not period-lastdelta. Thanks @Betlista]

Answer 3

The fastest solution proposed by Boris Strandjev has some problem by generating output of large numbers in Java. It is the fastest algorithm for finding number of divisors for very big integer in Java.

Here is my code which will run successfully:

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

}

This code is generally taking array of number as input and thereby multiplying which will produce large numbers. And, after that main code for counting number of divisor (including number is taken as divisor here) is done and given output.

I hope it is efficient way and suggest any errors or addition if needed.