The solutions of the Mordell curve $y^2=x^3+k$ with NON-POSITIVE $x$-value can be efficiently found by brute force. This can be reformulated as follows : $k$ is the sum of a square and a (non-negative) cube (with possible values $0$ and $1$). In other words : $y^2+z^3=k$ is solveable in non-negative integers.
Is there an easy criterion whether a given positive integer $k$ is the sum of a square and (non-negative) cube ? Or is brute force unavoidable ?