Для разложения числа на множители проверяют не все варианты подряд, а только простые числа. Таблицу можно подготовить заранее или генерировать в программе. Для разложения числа N0 надо проверять простые числа до N01/2 включительно. После каждого найденного множителя текущее значение Ni делится на него и перебор простых чисел начинается сначала.
Получается разложение вида
N0 = p1n1·p2n2·...·pknk, где pi - все простые числа от 2 до N01/2.
Количество различных делителей K получается как количество комбинаций степеней
K = (n1+1)·(n2+1)·...·(nk+1)
На примере:
N0 = 72
Простые числа до 721/2: pi = [2, 3, 5, 7]
Инициализируем счётчики степеней: ni = [0, 0, 0, 0]
72 на 2 делится, n1 = 1, проверяем 72/2 = 36
36 на 2 делится, n1 = 2, проверяем 36/2 = 18
18 на 2 делится, n1 = 3, проверяем 18/2 = 9
9 на 2 не делится
9 на 3 делится, n2 = 1, проверяем 9/3 = 3
3 на 2 не делится
3 на 3 делится, n2 = 2, 2/3 = 1, закончили поиск.
Получили массив степеней: ni = [3, 2, 0, 0]
Количество делителей: K = (3+1)·(2+1)·(0+1)·(0+1) = 12