HDU 1016

久しぶりに検索をしました。ほとんどできません。滔々とした問題解決報告を読んでやっと書き上げた。
http://blog.csdn.net/chuck_0430/articale/detail/8127339
深度検索の中心となるvisマーク配列の変化は、中間再帰的にdfsを呼び出します。

#include <cstdio>
#include <iostream>
#include <cstring>

#define NUMBER 500000  
#define LEN 1000000  

using namespace std;

int primelist[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1};
int n;
int num[21], vis[21];

/*      
long long prime[LEN];  
      
void primelist(long long* prime, long long* k) {  
    int j, n;  
    (*k) = 0;  
    prime[(*k)++] = 2;  
    for(n = 3; n <= NUMBER; n++) {  
        for(j = 0; prime[j]*prime[j] <= n; j++) {  
            if(n%prime[j] == 0) {  
                break;  
            }  
        }  
        if(prime[j]*prime[j] > n) {  
            prime[(*k)++] = n;  
        }  
    }  
}  
*/

void dfs(int cur) {
	int i, j;
	if(n == cur && (primelist[num[0]+num[n-1]])) {
		printf("1");
		for(i = 1; i < n; i++) {
			printf(" %d", num[i]);
		}
		printf("
");
	}
	else {
		for(i = 2; i <= n; i++) {
			if(primelist[i+num[cur-1]] && !vis[i]) {
				vis[i] = 1;
				num[cur] = i;
				dfs(cur+1);
				vis[i] = 0;
			}
		}	
	}
}

int main() {
	int cse = 1;
	num[0] = 1;
	while(scanf("%d", &n) != EOF) {
		printf("Case %d:
", cse++);
		memset(vis, 0, sizeof(vis));
		dfs(1);	
		printf("
");
	}
	return 0;
}