How to Count the Factors of a Number
Count the total, even, or odd factors of a number using prime factorization and the (a+1) product formula, with a worked example.
Expected Interview Answer
The number of factors of N is found by writing its prime factorization N = p1^a1 × p2^a2 × ... × pk^ak, then multiplying (a1+1)(a2+1)...(ak+1) — one more than each exponent, multiplied together.
This works because any factor of N is formed by choosing an exponent from 0 to ai for each prime pi independently, giving (ai+1) choices per prime, and the total factor count is the product of independent choices across all primes. The sum of all factors uses a related formula: for each prime, sum the geometric series 1+p+p^2+...+p^a, then multiply those sums across all primes. To count only even factors, force at least one factor of 2 by using a1 (not a1+1) for that prime while keeping (ai+1) for the rest; for odd factors, drop the prime 2 entirely before applying the formula.
- Turns factor-counting into one formula from the prime factorization
- Extends directly to sum-of-factors and even/odd factor variants
- Avoids manually listing every factor for large numbers
AI Mentor Explanation
Building a valid batting lineup where each of 3 all-rounders can bat in one of 4 possible positions independently gives 4 choices per player, so the total number of distinct lineups is 4 multiplied across all 3 players, not added. Counting factors of N works identically: for each prime factor with exponent a, there are (a+1) independent exponent choices (0 through a), and the total factor count is the product of those choices across every prime, exactly like multiplying independent lineup options.
Worked example
Prime factorization
- 720 = 2^4 × 3^2 × 5^1
Apply formula
- (4+1)(2+1)(1+1)
- = 5 × 3 × 2
Total factors
- = 30
Step-by-Step Explanation
Step 1
Find the prime factorization
Express N as p1^a1 × p2^a2 × ... × pk^ak.
Step 2
Add 1 to each exponent
Each prime independently contributes (ai + 1) exponent choices.
Step 3
Multiply the results
Total factor count = (a1+1)(a2+1)...(ak+1).
Step 4
Adapt for variants
For even factors, fix at least one power of 2; for odd factors, drop 2 from the factorization first.
What Interviewer Expects
- Correct prime factorization of N
- Correct application of the (a+1) product formula
- Understanding why the formula counts independent exponent choices
- Correct adaptation for even-only, odd-only, or perfect-square factor variants
Common Mistakes
- Forgetting to add 1 to each exponent before multiplying
- Using an incomplete or incorrect prime factorization
- Confusing factor count with sum of factors (different formulas)
- Mishandling the even/odd factor variant by not adjusting the exponent range correctly
Best Answer (HR Friendly)
“I start by finding the prime factorization of the number. Each prime's exponent gives one more than itself as the number of independent choices for that prime in any factor, so I add one to every exponent and multiply those together to get the total factor count. The same idea extends to sum-of-factors and even/odd-factor variants with small tweaks to the formula.”
Follow-up Questions
- How would you find the sum of all factors of N, not just the count?
- How many factors of N are perfect squares?
- How do you count only the even factors of a number?
- How would you find the number of ways to write N as a product of two factors?
MCQ Practice
1. How many factors does 360 have? (360 = 2^3 × 3^2 × 5^1)
(3+1)(2+1)(1+1) = 4×3×2 = 24.
2. How many factors does 100 have? (100 = 2^2 × 5^2)
(2+1)(2+1) = 3×3 = 9.
3. What is the correct formula for total factors of N = p1^a1 × p2^a2?
Each prime independently contributes (a+1) exponent choices, and independent counts multiply.
Flash Cards
Formula for number of factors of N? — Product of (ai + 1) over all primes in the factorization.
Why add 1 to each exponent? — Each prime's exponent can independently be 0 through ai — that is (ai+1) choices.
How to count only odd factors? — Drop the prime 2 entirely, then apply the formula to the rest.
How to count only even factors? — Total factors minus odd factors, or fix ≥1 power of 2 and vary the rest.