Алгоритмы и структуры данных

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

Простейший способ найти количество делителей положительного числа n — перебрать все числа от 1 до n и посчитать, какие из них делят n без остатка.
Однако такой подход работает очень медленно. Можно найти количество делителей, используя простые множители числа n (причём поиск самих простых множителей занимает лишь время порядка ).
Представим, что у нас есть число, записанное в виде произведения его простых множителей:
Чтобы узнать количество делителей n, нужно взять все показатели степени, прибавить к каждому по 1 и перемножить полученные результаты:
Реализовать это можно очень похоже на процесс нахождения простых множителей для 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 ≤ ).

Вывод

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

Примеры

Ввод
Вывод
8
4
17
2
2048
12
48
10
Бонус: почему, прибавляя к каждому показателю степени по 1 и перемножая результаты, мы получаем общее число делителей?</strong>
Идея формулы для подсчёта количества делителей числа n основана на том, что количество делителей связано с комбинациями простых множителей. Показатель степени каждого простого множителя показывает, сколько раз он может участвовать в произведении, образующем делитель числа n. Прибавляя 1 к каждому показателю, мы учитываем и «0 использований» данного простого множителя, что позволяет включить в общее число делителей и само n, и 1. Итоговое произведение (из (показатель + 1) для каждого простого множителя) показывает количество всех возможных сочетаний простых множителей и даёт общее число делителей n.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue