6
$\begingroup$

Given a integer $n$, we want to know if $n=m^k$ for some $m$ and $k>1$. What is the fastest method? (Suppose the factors of $n$ are not given).

The best method I can think of is to try to calculate $n^\frac{1}{k}$ to a certain precision, for $k$ from $2$ to $\log_2 n$. Determine if $n^\frac{1}{k}$ is a integer by test if $\lfloor n^\frac{1}{k} \rfloor ^k = n$.

  • 1
    The method you wrote down is __very__ fast. (Except there is no need to reraise it to the power $k$, just check the distance to nearest integer, and see if that is within the error tolerance of the $k^{th}$ rooting algorithmP) What are you doing that needs this to be faster? Whatever your program, it seems unlikely that this is the limiting factor for computation speed.2011-02-17

1 Answers 1

2

Like Jonas Meyer said, the mathoverflow post contains all the information.

The problem can be solved in almost linear time by this paper.