divisor (idea)

There is a little nice theorem which allows us to find how many divisors a number has, if we know its Prime Factorization.

Consider an integer number, n.
Suppose n = (p₁)^a₁ * (p₂)^a₂ * ... * (p_k)^a_k
,where p₁...p_k are prime numbers, and a₁...a_k are the corresponding exponents.

Then, you can easily find out how many divisors n has (say S), with the following simple formula:

S = (a₁+1)*(a₂+1)*...*(a_k+1)

---

Proof

Suppose as above n = (p₁)^a₁ * (p₂)^a₂ * ... * (p_k)^a_k

The divisors of the number n then are those with prime factorizations with the same primes as n but with powers no bigger than the powers a_i. Each power can be chosen independently, so there are (a₁+1)(a₂+1)...(a_k+1) such divisors.

---

Let's see that through an example. Consider 24.
24 = 2³ * 3¹
So, with the above formula we take (3+1)*(1+1) = 8 divisors
Let's check this.
Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
OK, they are 8.

Source: The Papyrous, Larousse, Britannica Encyclopedia