How to achieve a perfect square 
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$).

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}$.

