A number $c$ is given. We need to find a number $0<k<c$ such that
$c^2 - k^2$ is a perfect square. (if it is possible)
$c$ and $k$ can be any positive integer.
What I tried is-
I iterated for all the values $[1,c-1]$ and stopped at the first $k$ which satisfies the condition.
The Euclid's method to find a Pythagorean triple which takes O(c0.5) run time. We do not actually find a solution. But, we just need to check if it is possible or not.
Can the solution be better than this? What I am looking for is a more efficient solution. Maybe some algebraic formula or proof.