Кількість дільників (Розбір)

Позначимо через $d(n)$ кількість дільників числа $n$. Очевидно, що d(1) = 1.

Нехай $p$ — просте число. Тоді $p$ має два дільники: $1$ і $p$. Отже, d(p) = 2.

Нехай n = p^k — степінь простого числа. Тоді $n$ має k + 1 дільників: 1, p, p_2, p_3, ..., p^k. Отже, d(p^k) = k + 1.

Нехай n = p^k q^l. Розглянемо дві множини: P = {1, p, p_2, p_3, ..., p_k} і Q = {1, q, q_2, q_3, ..., q_l}

Будь-який дільник $d$ числа p^k q^l можна представити у вигляді x \cdot y, де x \in P, y \in Q. Дільник $x$ з $P$ можна вибрати k + 1 способом, дільник $y$ з $Q$ можна вибрати l + 1 способом. Відповідно, дільник d = x \cdot y можна скласти (k + 1) \cdot (l + 1) способами.

Розкладемо число $n$ на прості множники: n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}. Кількість дільників числа $n$ дорівнює

Приклад

Число n = 18 має $6$ дільників: 1, 2, 3, 6, 9, 18.

Розкладемо число n = 18 на прості множники:

Отже

Віднімаємо два дільники ($1$ і $18$), отримуємо відповідь: $4$ дільники.

Реалізація алгоритму

Функція CountDivisors розкладає число $n$ на прості множники і обчислює кількість його дільників $d(n)$.

int CountDivisors(int n)
{
  int c, i, res = 1;
  for(i = 2; i * i <= n; i++)
  {
    if (n % i == 0)
    {
      c = 0;
      while(n % i == 0)
      {
        n /= i;
        c++;
      }
      res *= (c + 1);
    }
  }
  if (n > 1) res *= 2;
  return res;
}

Основна частина програми. Читаємо вхідне значення $n$.

scanf("%d",&n);

Обчислюємо і виводимо відповідь. Із загальної кількості дільників $d(n)$ віднімаємо два дільники: $1$ і саме число $n$.

printf("%d\n",CountDivisors(n)-2);

Python реалізація

import math

Функція CountDivisors розкладає число $n$ на прості множники і обчислює кількість його дільників $d(n)$.

def CountDivisors(n):
  res = 1;
  for i in range(2, int(math.sqrt(n)) + 1):
    if (n % i == 0):
      c = 0
      while (n % i == 0):
        n //= i
        c += 1
      res *= (c + 1);
  if (n > 1): res *= 2;
  return res;

Основна частина програми. Читаємо вхідне значення $n$.

n = int(input())

Обчислюємо і виводимо відповідь. Із загальної кількості дільників $d(n)$ віднімаємо два дільники: $1$ і саме число $n$.

print(CountDivisors(n) - 2)