AdvancedQuantitative Aptitude · Lesson 19 of 25 · Updated ·
Factors, Divisors and Trailing Zeros — Count Them Without Listing
A factor (or divisor) of a number N is a whole number that divides N with no remainder. The factors of 12 are 1, 2, 3, 4, 6 and 12.
Listing factors works for 12. It does not work for 3,600 in a timed test. This lesson shows how to count factors, and how to count the zeros at the end of a big number like 100!, using one idea: prime factorisation.
1. Prime factorisation first
Write the number as a product of primes with powers:
- 72 = 2³ × 3²
- 360 = 2³ × 3² × 5
- 3,600 = 2⁴ × 3² × 5²
Divide by 2 as long as you can, then 3, then 5, then 7, and so on. Everything in this lesson starts here.
2. Number of factors
If N = pᵃ × qᵇ × rᶜ (p, q, r different primes), then the number of factors = (a + 1)(b + 1)(c + 1).
Why it works. Every factor of 72 = 2³ × 3² looks like 2ⁱ × 3ʲ. The power i can be 0, 1, 2 or 3 (4 choices). The power j can be 0, 1 or 2 (3 choices). Each pair of choices gives a different factor, so there are 4 × 3 = 12 factors. The "+1" is the choice of power 0.
Example 1 (TCS NQT style)
How many factors does 360 have?
360 = 2³ × 3² × 5¹. Factors = (3 + 1)(2 + 1)(1 + 1) = 4 × 3 × 2 = 24.
3. Even, odd and perfect-square factors
Odd factors: an odd factor has no 2 in it. So drop the power of 2 and count the rest.
Even factors: total factors − odd factors. (Or: the power of 2 must be at least 1, so it has a choices instead of a + 1.)
Perfect-square factors: in a square, every prime has an even power. For 2³ the even choices are 2⁰ and 2² (2 choices); for 3² they are 3⁰ and 3² (2 choices).
Example 2
For 360 = 2³ × 3² × 5, find the number of odd, even and perfect-square factors.
- Odd: use 3² × 5 only → 3 × 2 = 6 (1, 3, 5, 9, 15, 45)
- Even: 24 − 6 = 18 (check: 3 × 3 × 2 = 18, with the power of 2 chosen from 1, 2, 3)
- Perfect squares: 2 choices (2⁰, 2²) × 2 choices (3⁰, 3²) × 1 choice (5⁰) = 4 (1, 4, 9, 36)
4. Sum of factors
Sum of factors of pᵃ × qᵇ = (1 + p + p² + … + pᵃ) × (1 + q + … + qᵇ)
Why it works. Multiply the two brackets out. Each term of the result is one 2ⁱ × 3ʲ, so you get every factor exactly once.
Example 3
Find the sum of all factors of 72.
(1 + 2 + 4 + 8) × (1 + 3 + 9) = 15 × 13 = 195.
5. Writing N as a product of two numbers
Factors come in pairs: 72 = 1 × 72 = 2 × 36 = 3 × 24 = 4 × 18 = 6 × 12 = 8 × 9. With 12 factors there are 12 ÷ 2 = 6 pairs.
If N is a perfect square, one factor pairs with itself (144 = 12 × 12). Then the number of ways = (number of factors + 1) ÷ 2. For 144 = 2⁴ × 3² there are 5 × 3 = 15 factors, so 8 ways.
6. Trailing zeros of n!
n! (n factorial) = 1 × 2 × 3 × … × n. A trailing zero is a zero at the end of the number.
Each trailing zero comes from one 10 = 2 × 5. A factorial has far more 2s than 5s (every even number gives a 2), so the number of 5s decides the number of zeros.
Trailing zeros of n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … (⌊ ⌋ means "drop the decimal part")
Why the extra terms? 25 = 5 × 5 gives two fives. ⌊n/5⌋ counts one 5 from each multiple of 5. ⌊n/25⌋ adds the second 5 from 25, 50, 75 and so on.
Example 4 (Infosys / AMCAT style)
How many zeros are at the end of 250!?
⌊250/5⌋ + ⌊250/25⌋ + ⌊250/125⌋ = 50 + 10 + 2 = 62.
7. Highest power of any prime in n!
The same method (it is called Legendre's formula) works for any prime p: add ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … until the term becomes 0.
Example 5
Find the highest power of 3 that divides 50!.
⌊50/3⌋ + ⌊50/9⌋ + ⌊50/27⌋ = 16 + 5 + 1 = 22.
Example 6 (a composite divisor)
Find the highest power of 12 that divides 30!.
12 = 2² × 3. Count each prime separately:
- Power of 2 in 30!: 15 + 7 + 3 + 1 = 26. Each 12 needs two 2s → 26 ÷ 2 = 13.
- Power of 3 in 30!: 10 + 3 + 1 = 14.
The smaller one limits you: the answer is 13.
8. Trailing zeros of a product
Count the 2s and 5s in the whole product. The smaller count is the number of zeros.
How many zeros end 25 × 32 × 45 × 60?
| Number | 2s | 5s |
|---|---|---|
| 25 = 5² | 0 | 2 |
| 32 = 2⁵ | 5 | 0 |
| 45 = 3² × 5 | 0 | 1 |
| 60 = 2² × 3 × 5 | 2 | 1 |
| Total | 7 | 4 |
Zeros = min(7, 4) = 4. (The product is 21,60,000.)
Common mistakes
- Using the powers directly: 72 = 2³ × 3² has (3 + 1)(2 + 1) = 12 factors, not 3 × 2 = 6.
- Forgetting ⌊n/25⌋ and ⌊n/125⌋ in trailing-zero questions. 100! has 24 zeros, not 20.
- For a composite divisor like 12 or 6, counting only the largest prime. Count every prime and take the smallest result.
- Factorising wrongly. Multiply your prime factors back to check before you count.
Quick recap
- Factorise: N = pᵃ qᵇ rᶜ.
- Number of factors = (a + 1)(b + 1)(c + 1). Odd factors: ignore the 2. Even = total − odd.
- Square factors: only even powers. Sum of factors: multiply (1 + p + … + pᵃ) brackets.
- Pairs of factors = factors ÷ 2 (add 1 first if N is a perfect square).
- Trailing zeros of n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
- Power of prime p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + …; for a composite divisor, take the smallest.