Let $(x^2 + y)(y^2 + x) = p^5$, where $p$ is a prime. Then $x^2 + y = p^s$, $y^2 + x = p^t$, where $\{s, t\} = \{1, 4\}$ or $\{2, 3\}$. In the first case we can assume without loss of generality that $x < y$, $x^2 + y = p$ and $y^2 + x = p^4$. Then $p^2 = (x^2 + y)^2 > x + y^2 = p^4$, a contradiction.
Let $x < y$, $x^2 + y = p^2$ and $y^2 + x = p^3$. Note that $p > x$. We have $p^2|(x^2 + y)(x^2 - y) + (y^2 + x) = x^4 + x = x(x + 1)(x^2 - x + 1)$ and since $p > x$ we see that $p^2$ divides $(x + 1)(x^2 - x + 1)$. We consider two cases.

*Case 1.* If $p|x+1$ then $p = x+1$ and we easily find the solution $x = 2, y = 5$.

*Case 2.* If $p \nmid x+1$ then $p^2|x^2-x+1$ and now $p^2|x^2+y = (x^2-x+1)+(x+y-1)$ implies that $p^2$ divides $x+y-1$. Hence $y \ge p^2-x+1 > p^2-p$ and $p^3 = y^2+x > p^2(p-1)^2$ which is impossible.

Finally, the solutions are (2, 5) and (5, 2).