题目描述:

输入:

6
8

输出:

6
8

思路: 递归+回溯的应用

参考代码:

#include<iostream>
#include<string.h>
using namespace std;

//判断素数
int is_prime(int x) { //除1和其本身外,不能被其他整数所除.   一般因子i <= 根号x   i*i<= x
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0){
			return 0;
		}
	}
	return 1;
}

int n,A[50],vis[50],prime[50],case1;

void dfs(int cur){
	if(cur == n &&prime[A[cur-1]+A[0]]){
		for(int i = 0;i <n ;i++){
			if(i!=n-1){
				cout<<A[i]<<" ";
			}else{
				cout<<A[i];
			}
		}
		cout<<endl;
	}else{//递归+回溯 
		for(int i = 2; i <= n; i++){
			if(!vis[i]&&prime[i+A[cur-1]]){//判断是否成立 
				A[cur] = i;
				vis[i] = 1;//修改标记
				dfs(cur+1);
				vis[i] = 0; 
			}		
		} 
	}
	
}

int main(){
	while(scanf("%d",&n)!=EOF){
		//数据初始化
		memset(vis,0,sizeof(vis));
		if(case1){
			cout<<endl;
		}
		cout<<"Case "<<++case1<<":"<<endl;
		for(int i = 2; i <= 2*n; i++){//初始化素数数组 
			prime[i] = is_prime(i);
		} 
		A[0] = 1;
		dfs(1); 
	}
	return 0;
}