Як порахувати суму дільників числа?

АлгоритмиJunior~2 хв читання

Короткий відповідь

Щоб порахувати суму дільників числа n (зазвичай для n ≥ 1):

Швидко для одного числа: перебрати i від 1 до ⌊√n⌋, якщо i ділить n - додати i та n/i (якщо це різні числа). Складність O(√n).
Ідеально для багатьох запитів або дуже великих n: розкласти n на прості множники n = p1^a1 ⋯ pk^ak і використати формулу суми дільників: σ(n) = ∏ (p_i^(a_i+1) − 1) / (p_i − 1).

Докладний розбір

Визначення та застереження

Сума дільників σ(n) - сума всіх додатних дільників числа n, включно з 1 і n.
Сума власних дільників - це σ(n) − n (усі дільники, крім самого n).
Зазвичай визначаємо σ(n) лише для n ≥ 1. Для n ≤ 0 - або помилка вводу, або беремо σ(|n|). Для n = 0 дільників нескінченно багато - задача некоректна.

Підходи

Наївний перебір O(n): пройти по всіх i від 1 до n і підсумувати ті, що ділять n. Просто, але повільно.
Перебір до √n O(√n): якщо i | n, то n/i - теж дільник. Перебираємо i = 1..⌊√n⌋ і додаємо пару дільників одразу. Якщо i² = n, додаємо i один раз.
Через прості множники та формулу: якщо n = ∏ p_i^{a_i}, то σ(n) = ∏ ((p_i^{a_i+1} − 1) / (p_i − 1)). Для факторизації можна використовувати пробне ділення до √n, решето для набору запитів або більш просунуті методи для дуже великих n.

Приклади (n = 36)

Дільники: 1, 2, 3, 4, 6, 9, 12, 18, 36. Сума = 91. Розклад: 36 = 2^2 ⋅ 3^2, тоді σ(36) = (1+2+4) ⋅ (1+3+9) = 7 ⋅ 13 = 91.

Код (JavaScript)

O(√n) перебір дільників

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; // додаємо пару, якщо це не корінь
    }
  }
  return sum;
}

function sumProperDivisorsSqrt(n) {
  if (n === 1) return 0; // власні дільники 1 - порожня множина
  return sumDivisorsSqrt(n) - Math.abs(n);
}

// Приклади
console.log(sumDivisorsSqrt(36)); // 91
console.log(sumDivisorsSqrt(13)); // 14 (1 + 13)
console.log(sumProperDivisorsSqrt(28)); // 28 (досконале число)

Через розкладання на прості множники + формула

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; // масив пар [просте, степінь]
}

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) {
    // Геометрична прогресія: 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; // безпечно для помірних n
    const term = (termNum - 1) / (p - 1);
    result *= term;
  }
  return result;
}

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

Версія для великих чисел з BigInt (коли результат не вміщується в 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;

  // Факторизація пробним діленням (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))); // приклад великого результату

Який метод обрати

Один запит, середні n (до ~1e12 у JS з обережністю): O(√n) перебір - просто і швидко.
Багато запитів в обмеженому діапазоні: попередньо порахувати прості (решето), потім факторизувати швидше та використати формулу.
Дуже великі числа або суми, що потенційно не вміщуються: реалізація з BigInt.

Підводні камені та перевірки

Не забувайте додавати пару дільника n/i і не подвоювати корінь, якщо i² = n.
n = 1: σ(1) = 1, сума власних дільників = 0.
n ≤ 0: зазвичай беремо |n|, але формально задача ставиться для n ≥ 1. n = 0 - некоректно.
Переповнення Number у JS: для великих n використовуйте BigInt.

Складність

Перебір до √n: час O(√n), пам'ять O(1).
Факторизація пробним діленням: у найгіршому випадку O(√n), але в середньому швидше, далі формула рахується за O(k), де k - кількість різних простих множників.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.