题解 | #Prime Ring Problem#

Prime Ring Problem

#include <iostream>
#include <cstring>

using namespace std;

int n, a[20];
bool st[20];
int cnt;

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

void dfs(int k)
{
	if(k == n + 1 && isprime(a[n] + a[1]) && a[1] == 1)
	{
		for(int i = 1; i <= n; i ++) 
        {
            printf("%d", a[i]);
            if(i != n) printf(" ");
        }
		puts("");
	}
	
	for(int i = 1; i <= n; i ++)
	{
		if(!st[i] && (k == 1 || isprime(i + a[k - 1])))
		{			
			a[k] = i;
			st[i] = true;
			dfs(k + 1);
			st[i] = false;
		}
	}
}

int main()
{
    int k = 0;
    while(~scanf("%d", &n))
    {
        if(k ++) puts("");
        printf("Case %d:\n", ++ cnt);
        memset(st, 0, sizeof st);
        memset(a, 0, sizeof a);
        dfs(1);
    }
    
    return 0;
}