1

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

Álvaro G. Tenorio
  • 991
  • Why is that slow? Seems like it's already done? I mean, that's what $k$ is,. Anything else would have to be equivalent to this. – lulu Feb 26 '18 at 12:19
  • Yes, the answer is right, but we need a better (faster) way to compute it so the automatic judge that will correct the program don´t run out of time. – Álvaro G. Tenorio Feb 26 '18 at 12:25
  • 1
    Then this is not a math question but a programming one. For instance, if your prime factoring is unnecessarily slow then your entire program will be slow even though you might be using the indended approach. If you add your actual code to the question post, I'm sure either stackoverflow or code review (I'm not certain which would be best) is a better place. – Arthur Feb 26 '18 at 12:27

1 Answers1

3

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}$.
Bernard
  • 175,478