Lista

#include <iostream>

using namespace std;

bool *sieve;
int *ans;
int amo;


void swap(int a, int b)
{
	if (a == b) return;
	int t = ans[a];
	ans[a] = ans[b];
	ans[b] = t;
}
bool recurse(int pos)
{
	for (int other = pos; other >= 0; other -= 2)
	{
		if (sieve[(ans[other] + ans[pos + 1]) / 2]) continue;
		if (pos == 0) return true;
		swap(pos, other);
		if (recurse(pos - 1)) return true;
		swap(pos, other); //swap back
	}
	return false;
}

int main() {
    cin >> amo;
    ans = new int[amo];
    sieve = new bool[amo];

	for (int i=0; i<amo; i++) { 
		sieve[i] = false;
		ans[i] = i+1;
	}

	int maxPrime = amo * 2;
	for (int mul = 3; (mul * mul) < maxPrime; mul += 2)
	{
		for (int hole = mul / 2 + mul; hole < amo; hole += mul)
		{
			sieve[hole] = true;
		}
	}


	if (recurse(amo - 2))
	{
		for (int i=0; i<amo; i++) {
			cout << ans[i];
			cout << ' ';
		}
		cout << endl;
	}

	delete[] sieve;
	delete[] ans;

}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 2, 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED