Количество делителей при помощи разложения на простые множители

Простейший способ найти количество делителей положительного числа n — перебрать все числа от 1 до n и посчитать, какие из них делят n без остатка.

Однако такой подход работает очень медленно. Можно найти количество делителей, используя простые множители числа n (причём поиск самих простых множителей занимает лишь время порядка $\mathcal{O}(\sqrt{n})$ ).

Представим, что у нас есть число, записанное в виде произведения его простых множителей:

\begin{aligned} 2 &= 2^1 \\ 4 &= 2^2 \\ 7 &= 7^1 \\ 24 &= 2^3 \cdot 3^1 \\ 75 &= 3^1 \cdot 5^2 \\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 \\ 300 &= 2^2 \cdot 3^1 \cdot 5^2\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} \\ \end{aligned}

Чтобы узнать количество делителей n, нужно взять все показатели степени, прибавить к каждому по 1 и перемножить полученные результаты:

\begin{aligned} 2 &= 2^1 &&\implies 1 + 1 &&= 2\\ 4 &= 2^2 &&\implies 2 + 1 &&= 3\\ 7 &= 7^1 &&\implies 1 + 1 &&= 2\\ 24 &= 2^3 \cdot 3^1 &&\implies (3 + 1) \cdot (1 + 1) &&= 8\\ 75 &= 3^1 \cdot 5^2 &&\implies (1 + 1) \cdot (2 + 1) &&= 6\\ 84 &= 2^2 \cdot 3^1 \cdot 7^1 &&\implies (2 + 1) \cdot (1 + 1) \cdot (1 + 1) &&= 12\\ 300 &= 2^2 \cdot 3^1 \cdot 5^2 &&\implies (2 + 1) \cdot (1 + 1) \cdot (2 + 1) &&= 18\\ n &= p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot ... \cdot p_k^{e_k} &&\implies (e_1 + 1) \cdot (e_2 + 1) \cdot (e_3 + 1) \\ \end{aligned}

Реализовать это можно очень похоже на процесс нахождения простых множителей для n:

n = ...
p, divisors = 1, 1          # предполагаемый простой делитель и общее число делителей

while p * p <= n:           # пока p <= sqrt(n)
    p += 1                  # увеличиваем p на 1 на каждой итерации
    if n % p != 0:          # пропускаем, если n не делится на p
        continue
    
    exp = 0                 # счетчик для показателя степени
    while n % p == 0:       # делим, пока это возможно
        n //= p
        exp += 1
    divisors *= exp + 1     # обновляем произведение

if n > 1:                   # если p > sqrt(n) => n само по себе простой делитель
    divisors *= 2           # учитываем n как делитель с показателем степени 1
print(divisors)

Задача: Найти количество делителей `n`

Дано целое число n. Требуется найти количество делителей n.

Ввод

В первой строке содержится одно целое число n (2 ≤ n ≤ $10^9$ ).

Вывод

Необходимо вывести количество делителей числа n.

Примеры

Ввод	Вывод
8	4
17	2
2048	12
48	10

Бонус: почему, прибавляя к каждому показателю степени по 1 и перемножая результаты, мы получаем общее число делителей?</strong>

Идея формулы для подсчёта количества делителей числа n основана на том, что количество делителей связано с комбинациями простых множителей. Показатель степени каждого простого множителя показывает, сколько раз он может участвовать в произведении, образующем делитель числа n. Прибавляя 1 к каждому показателю, мы учитываем и «0 использований» данного простого множителя, что позволяет включить в общее число делителей и само n, и 1. Итоговое произведение (из (показатель + 1) для каждого простого множителя) показывает количество всех возможных сочетаний простых множителей и даёт общее число делителей n.

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB