How to find the minimum number N that is divisible by A to the power of N?

Question

Mathematics

FREE PASCAL. A is no more than 10000
For example A = 8
1^1 = 1
2^2 = 4
3^3 = 27
4^4 = 256 - divisible by A. It fits => N =
4 than 10^10, then an error was thrown. (because it went beyond real 2.9e-39 .. 1.7e+38, and other types were not available)
PS Available types integer, longint, real, string, array, boolean, byte, word

Answer 1

It's all about math.
First factorize A. Represent it as P(ai^pi), i=1..k, where ai are different primes.
(i.e. a1^p1 * a2^p2 * ... * ak^pk).
It is obvious that N must be sought in the form П(ai^qi), i=1..k. We need to find the degrees qi. How to do it?
N^N = P(ai^(N*qi)). Comparing with the formula for A and realizing that N^N must be at least A and divisible by it, we get the following constraint:
N*qi >= pi or qi*(ai^qi) >= pi for all i.
We need to find the minimum P(ai^qi) under the above restriction. Further, I think you can do it.

Answer 2

The search already involves enumeration.
But you can simplify it a little...
Approximately the following algorithm:
- we sort through all the numbers in the range 1 ... A-1, there is no point further, because the smallest number will be A itself.
Accordingly, in your example, 10 ^ 10 does not need to be multiplied, t .to. 8<10