Introduction

If you need the number of positive divisors of an integer in Java, the fastest practical exact method for one value is based on prime factorization. A naive loop from 1 to n works, but it wastes effort because divisor pairs make most checks unnecessary.

For single numbers, the best pattern is factorization plus the divisor-count formula. For many numbers in a range, you would switch to a sieve-based approach instead.

The Naive Method

This basic version is correct:

1public static int countDivisorsNaive(int n) {
2    int count = 0;
3    for (int i = 1; i <= n; i++) {
4        if (n % i == 0) {
5            count++;
6        }
7    }
8    return count;
9}

But it is O(n), which becomes slow for large inputs.

A Better Start: Scan to the Square Root

Divisors come in pairs. If i divides n, then n / i also divides n. That means you only need to test up to sqrt(n):

1public static int countDivisorsSqrt(int n) {
2    int count = 0;
3
4    for (int i = 1; i * i <= n; i++) {
5        if (n % i == 0) {
6            if (i * i == n) {
7                count += 1;
8            } else {
9                count += 2;
10            }
11        }
12    }
13
14    return count;
15}

This is already much faster than checking every number up to n.

The Prime Factorization Formula

If

n = p1^a1 * p2^a2 * ... * pk^ak

then the number of positive divisors is:

(a1 + 1) * (a2 + 1) * ... * (ak + 1)

So once you know the prime exponents, the divisor count is immediate.

Java Implementation

1public static int countDivisors(int n) {
2    if (n <= 0) {
3        throw new IllegalArgumentException("n must be positive");
4    }
5
6    int result = 1;
7    int remaining = n;
8
9    for (int p = 2; p * p <= remaining; p++) {
10        if (remaining % p == 0) {
11            int exponent = 0;
12            while (remaining % p == 0) {
13                remaining /= p;
14                exponent++;
15            }
16            result *= (exponent + 1);
17        }
18    }
19
20    if (remaining > 1) {
21        result *= 2;
22    }
23
24    return result;
25}

Example:

1public static void main(String[] args) {
2    System.out.println(countDivisors(36));   // 9
3    System.out.println(countDivisors(97));   // 2
4    System.out.println(countDivisors(100));  // 9
5}

For 36, the factorization is 2^2 * 3^2, so the answer is (2 + 1) * (2 + 1) = 9.

Why This Is Fast

The loop only tests candidate factors up to the square root of the shrinking remaining value. That makes it efficient for one exact query and far better than scanning all integers up to n.

It also counts divisors mathematically instead of enumerating them one by one. That is why the factorization version is the usual exact answer when the question is about speed for a single number.

When Many Queries Change the Answer

If you need divisor counts for many numbers up to a limit, repeated trial division stops being ideal. In that case, a sieve or smallest-prime-factor table is often faster overall because you precompute once and answer many queries cheaply.

So the practical rule is:

• one number: factorization method
• many numbers in a range: sieve-based method

That difference matters in competitive programming and number-theory utilities.

Common Pitfalls

• Looping all the way to n when a square-root bound is enough.
• Forgetting that perfect squares contribute only one divisor at the square root in the pair-count method.
• Using int when the input range should really be long.
• Ignoring the divisor-count formula after the number has already been factored.
• Forgetting to reject zero or negative inputs for a positive-divisor function.

Summary

• The naive divisor-count loop is correct but unnecessarily slow.
• A square-root scan is a solid optimization for one number.
• The best exact general method for one value is prime factorization plus the divisor-count formula.
• For many queries across a range, use a sieve-based strategy instead.
• Choose the algorithm based on workload, not just on code brevity.