#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; const int MAX_NUM = 34; bool isPrime[MAX_NUM + 1]; vector<int> path; vector<bool> used; int n; bool hasSolution = false; void initPrime() { fill(isPrime, isPrime + MAX_NUM + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= sqrt(MAX_NUM); ++i) { if (isPrime[i]) { for (int j = i * i; j <= MAX_NUM; j += i) { isPrime[j] = false; } } } } void backtrack(int step) { if (step == n) { if (isPrime[path[0] + path.back()]) { hasSolution = true; for (int i = 0; i < n; ++i) { cout << path[i]; if (i < n - 1) cout << " "; } cout << endl; } return; } for (int i = 2; i <= n; ++i) { if (!used[i] && isPrime[path.back() + i]) { used[i] = true; path.push_back(i); backtrack(step + 1); path.pop_back(); used[i] = false; } } } int main() { initPrime(); cin >> n; if (n == 1) { cout << "1" << endl; return 0; } if (n % 2 == 0) { used.resize(n + 1, false); path.push_back(1); used[1] = true; backtrack(1); } if (!hasSolution) { cout << "no answer" << endl; } return 0; }