Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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;
}
like image 689
Reg Avatar asked Apr 13 '12 10:04

Reg


People also ask

How do you find the number of factors quickly?

Finding the Number of FactorsStep 1: Do the prime factorization of the given number, i.e., express it as the product of primes. Step 3: Write the prime factorization in the exponent form. Step 3: Add 1 to each of the exponents. Step 4: Multiply all the resultant numbers.

What is the fastest way to find the factors of a large number?

To calculate the factors of large numbers, divide the numbers with the least prime number, i.e. 2. If the number is not divisible by 2, move to the next prime numbers, i.e. 3 and so on until 1 is reached. Below is an example to find the factors of a large number.


1 Answers

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 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
like image 116
Boris Strandjev Avatar answered Nov 15 '22 02:11

Boris Strandjev