Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як порахувати суму дільників числа?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Щоб порахувати суму дільників числа 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 дільників нескінченно багато - задача некоректна.

### Підходи

1. Наївний перебір O(n): пройти по всіх i від 1 до n і підсумувати ті, що ділять n. Просто, але повільно.
2. Перебір до √n O(√n): якщо i | n, то n/i - теж дільник. Перебираємо i = 1..⌊√n⌋ і додаємо пару дільників одразу. Якщо i² = n, додаємо i один раз.
3. Через прості множники та формулу: якщо 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 - кількість різних простих множників.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати935 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.