Аналіз алгоритму

Позначимо через $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,\dots ,p^k\}$ та $Q=\{1,q,q^2,q^3,\dots ,q^l\}$

Будь-який дільник $d$ числа $p^k{q}^l$ можна представити у вигляді $x\ast y$, де $x\in P,y\in Q$. Дільник $x$ з $P$ можна вибрати $k+1$ способом, дільник $y$ з $Q$ можна вибрати $l+1$ способом. Отже дільник $d=x\ast y$ можна скласти $(k+1)\ast (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$ на прості множники:

$18=2\ast 3^2$

Отже

Віднімаємо два дільники (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

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 = int(input())
print(CountDivisors(n) - 2)