IRL ABooklet

Assume such a colouring exists and consider the numbers $1, 3, 6, 8$. Any two of these numbers differ by a prime number: $3 - 1 = 2$, $6 - 1 = 5$, $8 - 1 = 7$, $6 - 3 = 3$, $8 - 3 = 5$ and $8 - 6 = 2$. Thus, at least four colours are needed.

To prove that four colours are sufficient, we pick four colours and number them $0, 1, 2, 3$. Colour number $i$ is applied to all integers $n$ that satisfy $n \equiv i \pmod 4$. The difference of any two integers of the same colour is then divisible by $4$, hence not a prime.