StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I can propose faster solution, though I have a feeling that it will not be fast enough yet. Your solution runs in <code>O(n)</code> and mine will work in <code>O(sqrt(n))</code>.</p> <p>I am going to use the fact that if n = x<sub>i1</sub><sup>p1</sup> * x<sub>i2</sub><sup>p2</sup> * x<sub>i3</sub><sup>p3</sup> * ... x<sub>ik</sub><sup>pk</sup> is the prime factorization of <code>n</code> (i.e. x<sub>i<sub>j</sub></sub> are all distinct primes) then n has (p1 + 1) * (p2 + 1) * ... * (pk + 1) factors in total.</p> <p>Now here goes the solution:</p> <pre><code>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); </code></pre> <p>This can be further optimized if you consider the case of 2 separately and then have the step for <code>x</code> equal to 2 not 1 (iterating only the odd numbers).</p> <p>Also note that in my code I modify <code>number</code>, you might find it more suitable to keep <code>number</code> and have another variable equal to <code>number</code> to iterate over.</p> <p>I suppose that this code will run reasonably fast for numbers not greater than 2<sup>64</sup>.</p> <p><strong>EDIT</strong> 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<sup>2</sup>, which was proposed by Betlista:</p> <ul> <li>If the algorithm is used as is the time taken is 57 seconds on my machine.</li> <li>If I consider only the odd numbers the time is reduced to 28 seconds</li> <li>If I change the check for the end condition of the <code>while</code> to comparing with the square root of <code>number</code> which I find using binary search the time taken reduces to 22 second.</li> <li>Finally when I tried switching all the <code>BigInteger</code>s with <code>long</code> the time was reduced to 2 seconds. As the proposed algorithm will not run fast enough for <code>number</code> larger than the range of <code>long</code> it might make sense to switch the implementation to <code>long</code></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload