Олимпиада задача про делители и числа

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

Приведу несколько наблюдений.
Возьмём какое-то число x. Оно имеет разложение на простые множители: x=p1^k1*p2^k2*...*pm^km.
Количество его делителей равно (k1+1)*(k2+1)*...*(km+1), это вроде бы очевидный факт (если нужно, могу расписать). Из этого следует, что:
1) количество делителей не зависит от конкретных значений p1..pm, т. е. если мы хотим сгенерировать число по количеству его делителей, то чтобы получить как можно меньшее число, мы хотим брать как можно меньшие p1..pm - это, очевидно, будут наименьшие m простых чисел;
2) количество делителей не зависит от того, возле каких pi стоят ki, так что для минимизации результата нам нужно бОльшие ki ставить при меньших pi

Из этого можно построить решение, основанное на переборе всех разбиений входного числа на произведение каких-то целых чисел: это разбиение по сути будет нашим (k1+1)*(k2+1)*...*(km+1). Нам нужно просто отнять от каждого члена произведения 1, отсортировать по убыванию (см. пункт 2) и возвести наименьшие m простых чисел в соответствующие степени.

Это явно будет побыстрее лобового перебора всех чисел, начиная с двойки, и подсчёта их делителей. Хотя даже в этом случае твой код считает количество делителей n за O(n), хотя с использованием того факта, что оно равно (k1+1)*(k2+1)*...*(km+1), этот поиск можно ускорить до O(sqrt n).

Требование про функции, конечно, убило. Я слышал, что олимпиадники пишут код по принципу "чукча не читатель, чукча писатель", но никогда бы не подумал, что говнокодить их учат целенаправленно. Интересно, зачем.