For any even number N, partition the integers from 1 to N into pairs such that the sum of the two numbers in each pair is a prime number.
Starting from the top, find the first pair $(N,N-k)$ with $k$ the least odd number for which the sum $2N-k$ is a prime. That takes care of pairs $(N,N-k),(N-1,N-k+1),\cdots$ and you are left with the numbers from $1$ to the even number $N-k-1$ which you can assume are doable by induction.
--> Actually any odd $k$ for which the sum of the pair $(N,N-k)$, i.e. $2N-k$, is prime will do for a starting block $(N,N-k),(N-1,N-k+1)$ for the partition, and choosing the largest such $k$ makes for the fewest "iterations" needed to make the partition.