How many positive integers are factors of a given number?

I've been trying to find / generate a formula for the following problem:

• Given a number, how many positive integers are factors of this number.

In practice, you could simply build a table as such (lets assume the number is 36):

1 | 36
2 | 18
3 | 12
4 | 9
6 | 6

Thus there are 9 positive integers that are factors to 36.

This method seems like it would be taxing if the number was large. So I was thinking that if you knew the prime factorization for a number such as $\,2 \cdot 2 \cdot 3 \cdot 3 = 36, \,$ there should be a formula for the number of unique combinations you can multiply these prime factors together. That's where I am stuck. Thanks in advance!

Solution 1:

Hint: if the prime factorization of $\,n\in\Bbb N\,$ is

$$n=\prod_{k=1}^rp_k^{a_k}$$

then the number of divisors of $\,n\,$ is

$$\prod_{k=1}^r(a_k+1)$$

Solution 2:

Consider this: Every positive integer has a unique prime factorisation, so choosing integers is the same as choosing prime factorisations. A prime factorisation divides another prime factorisation if and only if the exponents of each prime in the former are less than or equal to their counterparts in the latter.

So the number of divisors is the number of ways of choosing exponents satisfying that condition. For each prime $p^a$, I can choose any exponent between $0$ and $a$ inclusive – that's $a + 1$ choices. So, in conclusion: if \[n = \prod_{k = 1}^{N} p_k^{a_k}\] then \[\mathrm{\#factors}(n) = \prod_{k = 1}^N (a_k + 1)\]

Solution 3:

Alongside all the other replies here, I want to also offer a more visual/intuitive (at least for myself) explantion.

Consider the number whose prime factorization is: $$2(3^2)5$$

As others have shown, you need to finding the factors of this number involves finding the number of ways the prime factors of this number can be combined. One way is to view each possible exponent of a prime factor as a possible event and build a tree. I thought it would be hard to say it exactly, so below is a picture to describe the process.

http://i.stack.imgur.com/3ewkN.jpg

Looking at that you can see that the total number of 'events' is the product of all the events possible for each number - which is its exponent + 1 in the prime factorization. In the example above it's (1 + 1)(2 + 1)(1 + 1) = 12.

Once you have the intuition behind it, the formal definition feels a lot more approachable, at least for me. Hope it helps!