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

Программы составляют по готовым алгоритмам, если нужно искать эффективные алгоритмы, то обратитесь в начале к математикам.

О "рациональности" перебора речь вообще не идет, если перебирать 10^1000 значений по, скажем, 10^20 вариантов за секунду (явно мощнее, чем может себе позволить кто угодно на Земле - самый мощный компьютер на Земле, Tianhe-2, выдает где-то 34*10^15 операций с плавающей запятой в секунду) , то это займет намного больше, чем существует Вселенная.
Пойдем в обратную сторону. При каких условиях одно число - высокая степень чего-либо - будет делиться на другое? Видимо, речь пойдет о простых делителях. В какую степень не возводи 24, а на 25 оно делиться не начнет. Если представить N в виде 2^k1 * 3^k2 * 5^k3 * ...*pl^kl, то N^N будет выглядеть как 2^(k1*N) * 3^(k2*N) *... * p^(kl*N) - (*). Очевидно, что для делимости N^N на A необходимо и достаточно, чтобы в аналогичном представлении A = 2^m1 * 3^m2 * ...p^ml все показатели были меньше или равны соответствующим показателям из (*):ki*N>=mi (**). Вот, собственно, это и надо искать: разложить A на простые множители и найти минимальные значения их кратности (а это будет почти всегда 1, числа слишком быстро возрастают) , при которых выполняется соотношение (**).
Впрочем, я не уверен, что 1000-значное число можно быстро факторизовать. Там в общем случае придется порядка 10^500 потенциальных делителей перебрать. А без факторизации, очевидно, задача вообще не решается.