I need to find the number of factors of a large number $n^2$ that are less than $n$. Supposing I can find the prime factorization, it is simple to find the total number of factors as a combinatorial sum, but how do I enforce the inequality that the factors should be less than $n$?
[Math] Number of factors less than a number
combinatoricsfactoringnumber theory
Best Answer
Moving my comment to an answer:
For every factor $a$ of $n^2$ such that $a < n$ there is a factor $b = n^2/a$ that is greater than $n$. As @anon mentioned, it is important to not forget the boundary condition of $a = n$, where we would also have $b = n$. Thus, if it is "simple to find the total number of factors as a combinatorial sum", then just subtract one from this and divide by two. If you want to also count $n$ then add 1 back in after the division.