Дано натуральное число А. Найти такое минимальное натуральное N, что N^N делится на А без остатка.

Question

Как решить задачу боле рациональным способом, чем просто тупым подбором?

Answer 1

Разложить число на простые множители, взять каждый множитель по одному разу и перемножить. Если полученное число равно или превосходит кратность каждого отдельного простого множителя, то это число и есть искомое, если нет, то надо домножить это число на 2 и повторить процедуру.
 
P. S.
Блин, не уверен, что таким способом получится наименьше, ну ладно, теперь уже поздно что-то другое придумывать. Во всяком случае, я только такой путь пока вижу.