Count all divisors of a natural number

Problem

Given a positive integer n, return the total number of positive divisors of n (including 1 and n).

Examples

Example 1

Input: n = 25
Output: 3
Explanation: Divisors are 1, 5, 25.

Example 2

Input: n = 24
Output: 8
Explanation: Divisors are 1,2,3,4,6,8,12,24.

Notes

• The number-of-divisors function is multiplicative: if n = p1^e1 * p2^e2 * ... * pk^ek (prime powers) then the number of divisors is (e1+1)*(e2+1)*...*(ek+1).

Solution

Method 1 — Trial division factorization

Approach

1. If n == 1 return 1 (only divisor is 1).
2. Initialize ans = 1.
3. For p from 2 to floor(sqrt(n)):
   • If p*p > n break early.
   • Count cnt = 0 while n % p == 0: n /= p, cnt++.
   • If cnt > 0 then ans *= (cnt + 1).
4. After the loop, if n > 1 then n is a prime > sqrt(original n), multiply ans *= 2.
5. Return ans.

Edge cases:

• Works for n up to 64-bit range if you use 64-bit types; be careful with the loop limit (p*p <= n must use 64-bit multiplication).

Code

#include <vector>
using namespace std;

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;  // remaining prime factor
    return ans;
  }
};

Go

package main

type Solution struct{}

func (s *Solution) 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
}

Java

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;
  }
}

Kotlin

class Solution {
  fun countDivisors(n0: Long): Long {
    var n = n0
    if (n == 1L) return 1L
    var ans = 1L
    var p = 2L
    while (p * p <= n) {
      if (n % p == 0L) {
        var cnt = 0L
        while (n % p == 0L) { n /= p; cnt++ }
        ans *= (cnt + 1)
      }
      p++
    }
    if (n > 1L) ans *= 2L
    return ans
  }
}

Python

class Solution:
  def countDivisors(self, n: int) -> int:
    if n == 1:
      return 1
    ans = 1
    p = 2
    while p * p <= n:
      if n % p == 0:
        cnt = 0
        while n % p == 0:
          n //= p
          cnt += 1
        ans *= (cnt + 1)
      p += 1
    if n > 1:
      ans *= 2
    return ans

Complexity

• ⏰ Time complexity: O(sqrt(n)) in the worst case — we try divisors up to sqrt(n) and reduce n as we find factors.
• 🧺 Space complexity: O(1) extra space (ignoring input/output storage).

Method 2 — Sieve primes + factorization (best for multiple queries)

Precompute all primes up to sqrt(max_n) using a sieve once, then factor each query n by dividing only by those primes. This saves time when answering many queries or factoring large n repeatedly.

Approach

1. Use Sieve of Eratosthenes to generate primes up to floor(sqrt(maxN)).
2. For a given n, iterate primes p while p*p <= n and count exponents as in Method 1.
3. If n > 1 at the end, multiply the answer by 2.

Edge cases: handle n == 1 and ensure maxN is chosen large enough for all queries.

Code

C++

#include <vector>
using namespace std;

class Solution {
 public:
private:
  vector<int> sieve(int limit) {
    vector<char> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= limit; ++p) if (isPrime[p])
      for (int j = p * p; j <= limit; j += p) isPrime[j] = false;
    vector<int> primes;
    for (int i = 2; i <= limit; ++i) if (isPrime[i]) primes.push_back(i);
    return primes;
  }

public:
  long long countDivisors(long long n, const vector<int>& primes) {
    if (n == 1) return 1;
    long long ans = 1;
    for (int p : primes) {
      if (1LL * p * p > n) break;
      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;
  }
};

Go

package main

type Solution struct{}

func (s *Solution) sieve(limit int) []int {
  isPrime := make([]bool, limit+1)
  for i := range isPrime { isPrime[i] = true }
  isPrime[0], isPrime[1] = false, false
  for p := 2; p*p <= limit; p++ {
    if !isPrime[p] { continue }
    for j := p*p; j <= limit; j += p { isPrime[j] = false }
  }
  primes := []int{}
  for i := 2; i <= limit; i++ { if isPrime[i] { primes = append(primes, i) } }
  return primes
}

func (s *Solution) countDivisors(n int64, primes []int) int64 {
  if n == 1 { return 1 }
  ans := int64(1)
  for _, p := range primes {
    pp := int64(p)
    if pp*pp > n { break }
    if n%pp != 0 { continue }
    cnt := int64(0)
    for n%pp == 0 { n /= pp; cnt++ }
    ans *= (cnt + 1)
  }
  if n > 1 { ans *= 2 }
  return ans
}

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
  private List<Integer> sieve(int limit) {
    boolean[] isPrime = new boolean[limit + 1];
    java.util.Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= limit; ++p) if (isPrime[p])
      for (int j = p * p; j <= limit; j += p) isPrime[j] = false;
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= limit; ++i) if (isPrime[i]) primes.add(i);
    return primes;
  }

  public long countDivisors(long n, List<Integer> primes) {
    if (n == 1) return 1;
    long ans = 1;
    for (int p : primes) {
      if (1L * p * p > n) break;
      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;
  }
}

Python

class Solution:
  def _sieve(self, limit: int) -> list[int]:
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= limit:
      if is_prime[p]:
        for j in range(p * p, limit + 1, p):
          is_prime[j] = False
      p += 1
    return [i for i in range(2, limit + 1) if is_prime[i]]

  def countDivisors(self, n: int, primes: list[int]) -> int:
    if n == 1:
      return 1
    ans = 1
    for p in primes:
      if p * p > n:
        break
      if n % p != 0:
        continue
      cnt = 0
      while n % p == 0:
        n //= p
        cnt += 1
      ans *= (cnt + 1)
    if n > 1:
      ans *= 2
    return ans

Complexity

• ⏰ Time complexity (Method 2): sieve O(limit log log limit) to build primes plus O(#primes + factorization) per query; overall for limit = sqrt(maxN) and Q queries cost is O(limit log log limit + Q * sqrt(n)/log n) in practice.
• 🧺 Space complexity: O(limit) for the sieve and O(1) additional per query (excluding output).