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.
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;
}
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.
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.
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:
while
to comparing with the square root of number
which I find using binary search the time taken reduces to 22 second.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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With