1. Идея

Нужно посчитать количество натуральных делителей числа n.

Перебирать все числа от 1 до n слишком долго, потому что n может быть до 10^12.

Главная идея: делители удобно искать парами.

Если число i делит n, то существует парный делитель n / i.
Например, у числа 36:

• 1 и 36
• 2 и 18
• 3 и 12
• 4 и 9
• 6 и 6

Поэтому достаточно проверить числа только до sqrt(n).

2. Наблюдения

Наблюдение 1: делители идут парами

Если i является делителем n, то и n / i тоже является делителем.

Например, если 36 % 3 == 0, то 36 / 3 = 12, значит делители 3 и 12 появляются вместе.

Наблюдение 2: достаточно перебирать только до корня

Если i > sqrt(n), то соответствующий ему парный делитель n / i уже меньше sqrt(n) и был бы найден раньше.

Значит, можно проверять только i от 1 до тех пор, пока i * i <= n.

Наблюдение 3: полный квадрат нужно учитывать аккуратно

Если i * i == n, то делитель в паре один и тот же.

Например, для n = 36 число 6 образует пару само с собой, поэтому добавляем только 1, а не 2.

3. Алгоритм

1. Считать число n.
2. Завести переменную ans = 0.
3. Перебирать i от 1, пока i * i <= n.
4. Если n % i == 0, то:
   • если i * i == n, добавить к ответу 1;
   • иначе добавить 2, потому что найдены два делителя: i и n / i.
5. Вывести ans.

4. Почему это работает

Рассмотрим любой натуральный делитель числа n.

• Если он меньше sqrt(n), то мы найдём его напрямую в переборе.
• Если он больше sqrt(n), то ему соответствует парный делитель меньше sqrt(n), который тоже будет найден.
• Если делитель равен sqrt(n), это возможно только когда n — полный квадрат. Тогда такой делитель один, и его надо посчитать один раз.

Таким образом:

• ни один делитель не пропускается;
• ни одна пара делителей не считается дважды;
• для квадратов корректно обрабатывается центральный делитель.

Значит, алгоритм точно находит количество всех натуральных делителей числа n.

5. Сложность

Перебор идёт до sqrt(n).

• Время: O(sqrt(n))
• Память: O(1)

При n <= 10^12 это работает достаточно быстро.

6. Код на C++17

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long ans = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) {
                ans += 1;
            } else {
                ans += 2;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

ans = 0
i = 1
while i * i <= n:
    if n % i == 0:
        if i * i == n:
            ans += 1
        else:
            ans += 2
    i += 1

print(ans)