Для начала разберемся, какие простые множители входят в число и в каких степенях.

Теперь рассмотрим вид числа, которое является делителем и которое само делится на Пусть делится на тогда

где все принимают значения от до соответствующей степени в числе кроме которое принимает значения от до .

Следовательно, исходная задача свелась к подсчету различных чисел определенного вида. Посчитаем количество таких различных