Prove by induction.

The case $\displaystyle n=1$ is trivial.

Suppose that for $\displaystyle n = 1,2,\dots,m-1$, the integers $\displaystyle 1,2,\dots,2n-1,2n $ can be partitioned in pairs $\displaystyle (x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ s.t. $\displaystyle \forall j, x_j+y_j = prime. $

For $\displaystyle n=m$, we have the integers $\displaystyle 1,2,\dots,2m-1,2m$. By the Bertrand-Chebyshev theorem $\displaystyle \exists p=prime $ s.t. $\displaystyle 2m<p<4m \Longrightarrow p-2m<2m$**. **Therefore we have the following pairs:

$\displaystyle (p-2m,2m), (p-2m+1,2m-1),\dots, ((p-1)/2,(p+1)/2)$.

This takes care of the integers $\displaystyle p-2m$ to $\displaystyle 2m$. For the rest, note that $\displaystyle p-2m-1$ is an even number (odd-odd=even) and $\displaystyle p-2m-1<2m-1 \Longrightarrow p-2m-1 \le 2m-2 = 2(m-1)$. By the induction hypothesis, we can partition the remaining integers into pairs s.t. the sum of each pair is prime. Q.E.D.