How to calculate the sum of divisors of a number?

AlgorithmsJunior~3 min read

Short answer

To calculate the sum of divisors of a number n (usually for n ≥ 1):

Fast for a single number: iterate i from 1 to ⌊√n⌋, and if i divides n, add i and n/i (if they are different numbers). Complexity O(√n).
Ideal for many queries or very large n: factor n into primes n = p1^a1 ⋯ pk^ak and use the sum-of-divisors formula: σ(n) = ∏ (p_i^(a_i+1) − 1) / (p_i − 1).

Detailed breakdown

Definitions and caveats

The sum of divisors σ(n) is the sum of all positive divisors of n, including 1 and n.
The sum of proper divisors is σ(n) − n (all divisors except n itself).
σ(n) is usually defined only for n ≥ 1. For n ≤ 0 it is either an input error or σ(|n|) is used. For n = 0 there are infinitely many divisors - the task is undefined.

Approaches

Naive enumeration O(n): go through every i from 1 to n and sum the ones that divide n. Simple, but slow.
Enumeration up to √n, O(√n): if i | n, then n/i is also a divisor. Iterate i = 1..⌊√n⌋ and add the pair of divisors at once. If i² = n, add i only once.
Via prime factorization and the formula: if n = ∏ p_i^{a_i}, then σ(n) = ∏ ((p_i^{a_i+1} − 1) / (p_i − 1)). Factorization can use trial division up to √n, a sieve for many queries, or more advanced methods for very large n.

Example (n = 36)

Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36. Sum = 91. Factorization: 36 = 2^2 ⋅ 3^2, so σ(36) = (1+2+4) ⋅ (1+3+9) = 7 ⋅ 13 = 91.

Code (JavaScript)

O(√n) divisor enumeration

function sumDivisorsSqrt(n) {
  if (!Number.isInteger(n)) throw new Error("n must be integer");
  if (n === 0) throw new Error("sigma(0) is undefined (infinitely many divisors)");
  n = Math.abs(n);
  if (n === 1) return 1;

  let sum = 0;
  const limit = Math.floor(Math.sqrt(n));

  for (let i = 1; i <= limit; i++) {
    if (n % i === 0) {
      const j = n / i;
      sum += i;
      if (j !== i) sum += j; // add the pair unless it is the square root
    }
  }
  return sum;
}

function sumProperDivisorsSqrt(n) {
  if (n === 1) return 0; // proper divisors of 1 form an empty set
  return sumDivisorsSqrt(n) - Math.abs(n);
}

// Examples
console.log(sumDivisorsSqrt(36)); // 91
console.log(sumDivisorsSqrt(13)); // 14 (1 + 13)
console.log(sumProperDivisorsSqrt(28)); // 28 (a perfect number)

Via prime factorization + formula

function factorizeTrialDivision(n) {
  const factors = [];
  let x = n;

  let count = 0;
  while (x % 2 === 0) {
    x /= 2;
    count++;
  }
  if (count > 0) factors.push([2, count]);

  let p = 3;
  while (p * p <= x) {
    count = 0;
    while (x % p === 0) {
      x /= p;
      count++;
    }
    if (count > 0) factors.push([p, count]);
    p += 2;
  }

  if (x > 1) factors.push([x, 1]);
  return factors; // array of [prime, exponent] pairs
}

function sumDivisorsByFactorization(n) {
  if (!Number.isInteger(n)) throw new Error("n must be integer");
  if (n === 0) throw new Error("sigma(0) is undefined");
  n = Math.abs(n);
  if (n === 1) return 1;

  const factors = factorizeTrialDivision(n);
  let result = 1;
  for (const [p, a] of factors) {
    // Geometric progression: 1 + p + p^2 + ... + p^a = (p^(a+1) - 1)/(p - 1)
    let termNum = 1; // p^(a+1)
    for (let i = 0; i < a + 1; i++) termNum *= p; // safe for moderate n
    const term = (termNum - 1) / (p - 1);
    result *= term;
  }
  return result;
}

console.log(sumDivisorsByFactorization(36)); // 91
console.log(sumDivisorsByFactorization(1));  // 1

BigInt version for large numbers (when the result does not fit in Number)

function sumDivisorsBigInt(n) {
  if (typeof n !== 'bigint') n = BigInt(n);
  if (n === 0n) throw new Error("sigma(0) is undefined");
  n = n < 0n ? -n : n;
  if (n === 1n) return 1n;

  // Trial-division factorization (BigInt)
  const factors = [];
  let x = n;
  let count = 0n;
  while (x % 2n === 0n) { x /= 2n; count++; }
  if (count > 0n) factors.push([2n, count]);

  let p = 3n;
  while (p * p <= x) {
    count = 0n;
    while (x % p === 0n) { x /= p; count++; }
    if (count > 0n) factors.push([p, count]);
    p += 2n;
  }
  if (x > 1n) factors.push([x, 1n]);

  let result = 1n;
  for (const [pBig, aBig] of factors) {
    // p^(a+1)
    let pow = 1n;
    for (let i = 0n; i < aBig + 1n; i++) pow *= pBig;
    const term = (pow - 1n) / (pBig - 1n);
    result *= term;
  }
  return result;
}

console.log(String(sumDivisorsBigInt(999983n * 999983n))); // example of a large result

Which method to choose

A single query, moderate n (up to ~1e12 in JS, with care): O(√n) enumeration - simple and fast.
Many queries over a bounded range: precompute primes (a sieve), then factor faster and use the formula.
Very large numbers or sums that may not fit: the BigInt implementation.

Pitfalls and checks

Don't forget to add the paired divisor n/i, and don't double-count the root when i² = n.
n = 1: σ(1) = 1, sum of proper divisors = 0.
n ≤ 0: usually |n| is used, but formally the task is defined for n ≥ 1. n = 0 is undefined.
Number overflow in JS: use BigInt for large n.

Complexity

Enumeration up to √n: time O(√n), memory O(1).
Trial-division factorization: O(√n) in the worst case, but faster on average, after which the formula is computed in O(k), where k is the number of distinct prime factors.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.