C :

#include<stdio.h>
#include<string.h>
#include<math.h>

int n,a[20],v[21];

int prime(int m)
{
	int i;
	for(i=2;i<=sqrt(m);i++)
		if(m%i==0)
			break;
	if(i<=sqrt(m))
		return 0;
	return 1;
}

void dfs(int r)
{
	int i,j;
	if(r==n)
	{
		if(prime(a[r-1]+1))
		{
			for(j=0;j<n;j++)
				printf(j==n-1?"%d\n":"%d ",a[j]);
		}
		return;
	}
	for(i=2;i<=n;i++)
	{
		if(!v[i]&&prime(a[r-1]+i))
		{
			v[i]=1;
			a[r]=i;
			dfs(r+1);
			v[i]=0;
		}
	}
}

int main()
{
	int c=0;
	while(scanf("%d",&n)!=EOF)
	{
		printf("Case %d:\n",++c);
		if(n%2==0)
		{
			memset(v,0,sizeof(v));
			a[0]=v[1]=1;
			dfs(1);
		}
		puts("");
	}
	return 0;
}

C++ :

#include<stdio.h>
#include<string.h>
#include<math.h>

int n,a[20],v[21];

int prime(int m)
{
	int i;
	for(i=2;i<=sqrt(m);i++)
		if(m%i==0)
			break;
	if(i<=sqrt(m))
		return 0;
	return 1;
}

void dfs(int r)
{
	int i,j;
	if(r==n)
	{
		if(prime(a[r-1]+1))
		{
			for(j=0;j<n;j++)
				printf(j==n-1?"%d\n":"%d ",a[j]);
		}
		return;
	}
	for(i=2;i<=n;i++)
	{
		if(!v[i]&&prime(a[r-1]+i))
		{
			v[i]=1;
			a[r]=i;
			dfs(r+1);
			v[i]=0;
		}
	}
}

int main()
{
	int c=0;
	while(scanf("%d",&n)!=EOF)
	{
		printf("Case %d:\n",++c);
		if(n%2==0)
		{
			memset(v,0,sizeof(v));
			a[0]=v[1]=1;
			dfs(1);
		}
		puts("");
	}
	return 0;
}

Java :

import java.util.Scanner;


public class Main {
    static int cnt;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            if (n == 1) {
                System.out.println("Case " + ++cnt + ":\n");
                continue;
            }
            init(n);
            calc(n);
        }
    }

    private static void init(int n) {
        used = new boolean[n];
        N = new int[n];
    }

    private static void calc(int n) {
        System.out.println("Case " + ++cnt + ":");
        solve(0, n);
        System.out.println();
    }

    static boolean[] used;
    static int[] N;

    private static void solve(int pos, int n) {
        if (pos == n) {
            if (valid(N.length - 1)) {
                print();
            }
            return;
        }

        if (N[0] > 1) return;

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                N[pos] = i + 1;
                if (valid2(pos)) {
                    used[i] = true;
                    solve(pos + 1, n);
                    used[i] = false;
                }
            }
        }
    }

    private static void print() {
        for (int i = 0; i < N.length; i++) {
            if (i == 0) {
                System.out.print(N[0]);
                continue;
            }
            System.out.print(" " + N[i]);
        }
        System.out.println();
    }

    private static boolean valid(int len) {
        boolean flag = true;
        for (int i = 0; i < len; i++) {
            if (!isPrime(N[i] + N[i + 1])) {
                flag = false;
                break;
            }
        }


        return isPrime(N[N.length - 1] + N[0]) ? flag : false;
    }

    private static boolean valid2(int len) {
        boolean flag = true;
        for (int i = 0; i < len; i++) {
            if (!isPrime(N[i] + N[i + 1])) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    private static boolean isPrime(int n) {
        boolean flag = true;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                flag = false;
                break;
            }
        }

        return flag;
    }
}