524 - Prime Ring Problem

/*
+---------------------------------------------+
|                                             |
|       © 07/05/2024 (22:40) MinaMagdy        |
|                                             |
+---------------------------------------------+
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define endl "\n"
#define MOD 1000000007
#define INF 2000000000
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define sz(x) int(x.size())

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int n;
vector<int> tmp = {1};

void backtrack(int mask = 1, int prev = 1) {
    if (mask == (1 << n) - 1) {
        if (is_prime(prev + 1)) {
            for (int i = 0; i < n; i++) {
                cout << tmp[i] << " \n"[i == n - 1];
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) continue;
        if (is_prime(prev + i + 1)) {
            tmp.push_back(i + 1);
            backtrack(mask | (1 << i), i + 1);
            tmp.pop_back();
        }
    }
}

void solve() {
    int idx = 0;
    while (cin >> n) {
        if (idx)
            cout << endl;
        cout << "Case " << ++idx << ":\n";
        backtrack();
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}