Problem

Given a positive integer n, return the number of positive divisors (factors) of n.

Examples

Example 1

1
2
3

Input: n = 12
Output: 6
Explanation: 12 = 2^2 * 3^1 -> (2+1)*(1+1) = 6. Divisors: 1,2,3,4,6,12

Example 2

1
2
3

Input: n = 210
Output: 16
Explanation: 210 = 2*3*5*7 -> (1+1)^4 = 16

Solution

A naive check from 1 to n is too slow for large n. The common efficient approach uses prime factorization: if

n = p1^e1 * p2^e2 * ... * pk^ek

then the number of divisors is (e1+1)*(e2+1)*...*(ek+1).

Method 1 — Prime factorization (trial division)

Intuition

Only prime powers contribute to the factor-count multiplicatively. Finding exponents ei for each prime pi and computing the product (ei+1) yields the answer.

Approach

  • Maintain ans = 1.
  • For each prime p (or for each integer p starting from 2), count cnt = 0 while n % p == 0: increment cnt, divide n /= p.
  • Multiply ans *= (cnt + 1) if cnt > 0.
  • Stop once p*p > n. If remaining n > 1 it is a prime with exponent 1, so multiply ans *= 2.

Edge cases: n = 1 -> return 1 (only divisor is 1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
  long long countDivisors(long long n) {
    if (n <= 1) return 1;
    long long ans = 1;
    for (long long p = 2; p * p <= n; ++p) {
      if (n % p != 0) continue;
      int cnt = 0;
      while (n % p == 0) { n /= p; ++cnt; }
      ans *= (cnt + 1);
    }
    if (n > 1) ans *= 2;
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

package main

func countDivisors(n int64) int64 {
  if n <= 1 { return 1 }
  var ans int64 = 1
  for p := int64(2); p*p <= n; p++ {
    if n%p != 0 { continue }
    var cnt int64 = 0
    for n%p == 0 { n /= p; cnt++ }
    ans *= (cnt + 1)
  }
  if n > 1 { ans *= 2 }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public long countDivisors(long n) {
    if (n <= 1) return 1;
    long ans = 1;
    for (long p = 2; p * p <= n; ++p) {
      if (n % p != 0) continue;
      int cnt = 0;
      while (n % p == 0) { n /= p; ++cnt; }
      ans *= (cnt + 1);
    }
    if (n > 1) ans *= 2;
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
  fun countDivisors(nInput: Long): Long {
    var n = nInput
    if (n <= 1) return 1
    var ans = 1L
    var p = 2L
    while (p * p <= n) {
      if (n % p != 0L) { p++ ; continue }
      var cnt = 0L
      while (n % p == 0L) { n /= p; cnt++ }
      ans *= (cnt + 1)
      p++
    }
    if (n > 1) ans *= 2
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def count_divisors(self, n: int) -> int:
        if n <= 1:
            return 1
        ans = 1
        p = 2
        while p * p <= n:
            if n % p != 0:
                p += 1
                continue
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            ans *= (cnt + 1)
        if n > 1:
            ans *= 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub struct Solution;
impl Solution {
    pub fn count_divisors(mut n: u64) -> u64 {
        if n <= 1 { return 1 }
        let mut ans = 1u64;
        let mut p = 2u64;
        while p * p <= n {
            if n % p != 0 { p += 1; continue }
            let mut cnt = 0u64;
            while n % p == 0 { n /= p; cnt += 1 }
            ans *= cnt + 1;
            p += 1;
        }
        if n > 1 { ans *= 2 }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(sqrt(n)) in the worst case (trial division up to sqrt(n)), more precisely O(pi(sqrt(n))) if using primes, where pi(x) is number of primes ≤ x. For typical inputs this is fast for 64-bit n.
  • 🧺 Space complexity: O(1) extra memory (just counters and a few variables).

Method 2 — Count paired divisors up to sqrt(n)

Intuition

Every divisor d <= sqrt(n) pairs with n/d. Counting divisors by scanning d from 1 to floor(sqrt(n)) and incrementing by 2 when d divides n (or by 1 when d*d == n) gives the count without factorization.

Approach

  • Initialize cnt = 0.
  • For d from 1 to floor(sqrt(n)): if n % d == 0, then add 2 to cnt (for d and n/d) unless d * d == n in which case add 1.
  • Return cnt.

Edge cases: n = 0 is undefined for divisor counting (skip); n = 1 returns 1.

Code (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def count_divisors_sqrt(self, n: int) -> int:
        if n <= 0: return 0
        cnt = 0
        d = 1
        while d * d <= n:
            if n % d == 0:
                cnt += 1 if d * d == n else 2
            d += 1
        return cnt

Complexity

  • ⏰ Time complexity: O(sqrt(n)) — one loop up to sqrt(n).
  • 🧺 Space complexity: O(1).

Notes

  • For many queries or when n is very large, precomputing primes up to sqrt(max_n) (sieve of Eratosthenes) and trial dividing only by primes is faster.
  • The factorization method is preferable when n is large but factorable quickly (e.g., when n has small prime factors).