全排列+素数环（回溯）

参考链接：全排列+素数环

全排列 

#include <iostream> #include <set> #include <cstdio> #include <map> #include <cstring> #include <cstdio> #include <cctype> #include <queue> #include <vector> #include <malloc.h> #include <algorithm> #include <limits.h>//数据类型的最值常量 #include <cmath> #include <cctype> using namespace std; typedef long long LL; int n,box[20]; int vis[20]; void dfs(int step){ if(step==n+1){//开始确定不存在的下一位的时候停止 for(int i=1;i<=n;i++){ cout<<box[i]<<" "; } cout<<endl; } for(int i=1;i<=n;i++){ if(!vis[i]){ box[step]=i; vis[i]=1; dfs(step+1); vis[i]=0; } } } int main(){ cin>>n; dfs(1); return 0; }

素数环

 

#include <iostream> #include <set> #include <cstdio> #include <map> #include <cstring> #include <cstdio> #include <cctype> #include <queue> #include <vector> #include <malloc.h> #include <algorithm> #include <limits.h>//数据类型的最值常量 #include <cmath> #include <cctype> using namespace std; typedef long long LL; int n,box[25]; int vis[25]; int is_primer(int n){ for(int i=2;i<=sqrt(n);i++){ if(n%i==0){ return 0; } } return 1; } void dfs(int step){ if(step==n+1){ if(is_primer(box[step-1]+1)){ for(int i=1;i<=n;i++){ if(i!=1) cout<<" "; cout<<box[i]; } cout<<endl; return ; } } for(int i=1;i<=n;i++){ if(!vis[i]&&is_primer(box[step-1]+i)){ box[step]=i; vis[i]=1; dfs(step+1); vis[i]=0; } } } int main(){ int kase=0; while(cin>>n){ if(kase) cout<<endl; memset(vis,0,sizeof(vis)); box[1]=1; vis[1]=1; cout<<"Case "<<++kase<<":"<<endl; dfs(2); } }