[UVa] 524 - Prime Ring Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 524 - Prime Ring Problem
Source            : UVa Online Judge
Category          : Backtrack
Algorithm         : Backtrack
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
bool vis[20];
vector <int> List;
bool primeList[50];
 
bool isPrime(int n)
{
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n%2 == 0) return false;
    for (int i = 3; i*i <= n; i++)
        if (n%i == 0) return false;
    return true;
}
 
void SEIVE()
{
    for (int i = 0; i < 50; i++)
        primeList[i] = isPrime(i);
}
 
void backTrack(int last, int n)
{
    if (List.size() == n)
    {
        int sum= List[n-1] + 1;
        if (primeList[sum] == 0) return;
        for (int i = 0; i < n; i++)
        {
            printf("%d", List[i]);
            printf(i == n-1 ? "\n" : " ");
        }
        return;
    }
 
    for (int i = 2; i <= n; i++)
    {
        int sum = i + last;
        if (vis[i] || !primeList[sum]) continue;
 
        vis[i] = 1;
        List.push_back(i);
 
        backTrack(i, n);
 
        vis[i] = 0;
        List.pop_back();
    }
}
 
int main()
{
    SEIVE();
 
    int n;
    int tcase = 1;
    while (scanf("%d", &n) == 1)
    {
        fill(begin(vis), end(vis), 0);
        List.clear();
        List.push_back(1);
        if (tcase > 1) puts("");
        printf("Case %d:\n", tcase++);
        backTrack(1, n);
    }
}