Auto comment: topic has been updated by unknow754389 (previous revision, new revision, compare).

Ideia: For some number n search for the first i in [1, n] such that n + i is equal to a prime. If no answer exists then it's impossible (because n must be matched with someone). After that you can generate pairs

(n, i), (n-1, i+1), (n-2, i+2), ..., (i, n)

And you reduced the problem from n to i-1. The largest prime gape for numbers ≤ 1e5 is 34 (between 73,577 and 73,607), so basically all cases will reduce at most to the case where n ≤ 33. Then I did some small cases and simply guessforced that there would always be a solution and it passed. Hope this helps!