Proof or disproof that every integer can be written as the sum of a prime and a square.

I’m refreshing some algebra and in the beginning chapters of my book I’m presented with the following simple looking problem that I got stuck on:

Prove or disprove: If $n$ is a positive integer, then $n=p+a^2$, where $a$ is an integer and $p$ is prime or $p=1$.

At first I thought $n=13$ would give a nice counterexample, but then I noticed my book defines primes to include the negative primes. Now $13=-3+4^2$ is a solution.

I am allowed to use the fundamental theorem of arithmetic and the division and euclidean algorithms. I tried to express $n$ and $a$ by their prime factorizations, but I didn’t get anywhere from there. I would like a hint which direction to take. Am I just missing something silly?

Solutions Collecting From Web of "Proof or disproof that every integer can be written as the sum of a prime and a square."