Count divisors

Count all positive divisors of an integer efficiently using prime factors.

divisors prime factorization math counting

Write a function `count_divisors(n: int) -> int` that returns the number of positive divisors of a positive integer `n`.

For example, the number 12 has divisors 1, 2, 3, 4, 6, 12 — that's 6 divisors.

You must use the divisor count formula: if the prime factorization of `n` is `p1^a1 * p2^a2 * ... * pk^ak`, then the number of divisors is `(a1 + 1) * (a2 + 1) * ... * (ak + 1)`.

Implement the function efficiently — trial division up to the square root is fine. Do not simply loop from 1 to n counting divisors (that will be too slow for large n).

Constraints

- `1 <= n <= 10^9`
- Time: O(√n) worst-case, acceptable given the input bound.
- The function must return an integer.

Example

>>> count_divisors(12)
6
>>> count_divisors(1)
1
>>> count_divisors(100)
9
>>> count_divisors(997)  # prime number
2

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start from 2 and repeatedly divide n by its prime factors.

Each time you find a prime factor, count how many times it divides n.

If a prime factor has exponent a, multiply your answer by (a + 1).

After the loop, if n is greater than 1, it's a prime factor with exponent 1, so multiply by 2.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.