How to achieve a perfect square

Question

Given a natural number $n$, compute the smallest number $k$ such that $nk$ is a perfect square.

Obviously, I have tried factorizing the number so $n=p_1^{s_1}...p_r^{s_r}$ and $k=p_{i1}...p_{il}$ where $p_{ij}\in\{p_m:m\in\{1,...,r\}:s_m\text{ is odd}\}$. Unfortunatelly (and obviously) it is veeery slow, so I get a time limit veredict.

Also I have tried compute $S\mod n$ being $S$ a perfect square such that $S\geq n$, so the first $S$ with $S\mod n = 0$ is our answer ($k=S/n$).

Answer 1

Another solution, hopefully faster:

• Find the greatest square $m$ such that $m^2\mid n$.

You only have to test for $m\le\sqrt n$. Note the finite differences between two consecutive squares is just the sequence of odd integers $>1$, so it should be comparatively fast.

• Then set $\;k=\dfrac n{m^2}$.