Divisions

This problem asks us for the number of factors of a number.

Solution 1: brute force and pray

In this solution, we simply iterate up to root(n) and count the factors. We have to ensure we handle 1, 2, and perfect squares correctly. This is a bit tricky when dealing with doubles. The best way to check if a number is a perfect square is to root it, round that value, then square it and check if the value is equal. We have to ensure we correctly distinguish between a number that is a perfect square and one that has two factors an integer apart.

This solution is iffy at 10^9. We can double the speed by skipping even numbers, and get 1/3 the speed by only taking n where n%6 == 1 or 5 (aka not a multiple of 3 or 2). This may be fast enough

Solution 2: be smarter

If we have the prime factorization of a number, we can the number of factors is simply the number of combinations of each factor. For example, 180 = 2^2 * 3^2 * 5 has 18 factors (we can use the factor 2 either 0, 1, or 2 times (3 possibilities) and the same with 3. 5 has two possibilities ( 0 or 1 times) leading to 3 * 3 * 2 = 18. So it turns out all we need to do is prime factor the number. There is a cheat for this. Consider the following facts:

1. The largest single prime factor of any number n must be at most n^1/2
2. Any given number n which has no prime factors <= n^1/3 can have at MOST one distinct prime factor between n^1/3 and n^1/2. Proof: suppose two such prime factors (x and y) existed. Divide n by x and y, which must result in an integer since x and y are each prime factors, and the result must be less than n^1/3 since x,y > n^1/3. This is a contradiction of the premise. There is one corner case. Suppose that division == 1. This means that x and y are the only two factors of n, and one of them must necessarily be greater than n^1/2, OR n is a perfect square and x==y. QED.

This leads an easy optimization. Find the prime factorization up to n^1/3. If not all factors are found yet, divide n by the current factorization to get the other factor. This is plenty fast enough.

Notes: just iterate i from 1-> n^1/3 + some small epsilon to deal with rounding error (10^-6 or so). At each time, if n%i==0, set n=n/i and record the factor. Be sure to check i in case it divides the new n. If n ever == 1, terminate, as we've found all the factors. If we reach n^1/3 + epsilon, it means either the remaining n is a perfect square, in which case there is only a single remaining factor (trivially checkable), or n is prime (?????