5. Misha painted all integers in several colors such that numbers whose difference is a prime number are painted in different colors. What is the smallest number of colors that Misha could have used? Justify your answer.
5. Answer: 4 colors

Evaluation. Consider the numbers $1,3,6,8$. The difference between any two of them is a prime number, which means that all of them must be of different colors, and at least four colors are needed.

Example. Paint numbers of the form $4 \mathrm{k}$ in the first color, numbers of the form $4 \mathrm{k}+1$ in the second color, numbers of the form $4 \mathrm{k}+2$ in the third color, and numbers of the form $4 \mathrm{k}+3$ in the fourth color ( $\mathrm{k}$ - an integer). The difference between any two numbers of the same color is a multiple of 4 and cannot be a prime number.

Grading criteria:

Correct example provided: 3 points. Correct evaluation provided: 3 points.

Only the correct answer provided: 0 points.