Для "оптимизации" поиска числа делителей надо знать, что если
\(N = P_1^{a_1}\cdot . . . \cdot P_k^{a_k},\ где\ все\ P_i - \ различные\ простые\ числа, a_i > 0 \),
то число \(\Huge{\sigma}_{\large0}\large (N) = (a_1+1)\cdot(a_2+1)\cdot . . . \cdot(a_k+1)\) равно количеству всех делителей числа.
Доказать это не очень сложно, но пока примем это без доказательства.
Есть еще одна "полезная" формула, определяющая сумму всех делителей числа:
\(\Huge{\sigma}_{\large1}\large (N) = \frac{(P_1^{a_1+1}-1)}{p_1-1}\cdot\frac{(P_2^{a_2+1}-1)}{p_2-1}\cdot . . .\cdot\frac{(P_k^{a_k+1}-1)}{p_k-1}\)
Напишем программу, которая, для заданного N, будет вычислять значения \(\Huge{\sigma}_{\large0}\normalsize\ ,\ \Huge{\sigma}_{\large1} \)и список пар [(P1,a1), ... ,(Pk,ak)]
Программа будет использовать подпрограмму mindel