# Number of factors less than a number

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$?

-
Do you want the number of prime factors of $n^2$ or all of its factors? –  user12998 Aug 19 '11 at 2:50
@Robert, anon is right, I want the number of factors (i.e., divisors) of $n^2$ that are less than $n$. –  highBandWidth Aug 19 '11 at 3:02
For every $a$ factor of $n^2$ that is less than $n$ there is a factor $b = n^2/a$ that is greater than $n$. Thus, if it is "simple to find the total number of factors as a combinatorial sum", then why not just divide that by $2$ to get the number of factors less than $n$? –  Artem Kaznatcheev Aug 19 '11 at 3:22
@Artem, do you want to write that up as a an answer? –  highBandWidth Aug 19 '11 at 3:38
Let $n=\prod p_i^{a_i}$ where the $p_i$ are distinct primes. Then the number of divisors less than $n$ is $((\prod (2a_i+1)) -1)/2$. –  André Nicolas Aug 19 '11 at 3:40

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.

-

The sum of powers of divisors of a number $\sigma_k(n) = \sum_{d \ge 1, d \vert n} d^k$ could be used to find the number of divisors. It is known as divisor function. The number of divisors of $n^2$ is $\sigma_0(n^2)$.

Because for every divisor $d$, $\frac{n^2}{d}$ is also a divisor, hence we split the sum over divisor into $d=n$, $1 \le d < n$ and $n < d \le n^2$:

$$\sigma_0(n^2) = \sum_{d \ge 1, d \vert n^2} d^0 = 1 + 2 \sum_{n > d \ge 1, d\vert n} d^0$$

Thus the number you seek is $\frac{\sigma_0(n^2)-1}{2}$.

-