素数环
Time Limit:4000MSMemory Limit:65536KBTotal Submissions:172Accepted:79
Share
Description:
给定数n，在n的所有排列中，记a[1],a[2],...,a[n]，求满足a[i]+a[i+1](1<=i<=n-1)是素数并且a[1]+a[n]也是素数的所有排列。排列按字典序输出。
Input:
输入只有一行n (0 < n < 20).
Output:
按字典序输出答案
Sample Input:
8
Sample Output:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Source:
#include<stdio.h>
#include<iostream>
using namespace std;
#define NO 20
bool prime[]={0,1,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,0,0,0};
bool mark[NO];
int n;
int stack[NO],top;
void print()
{
printf("%d",stack[0]);
for(int i=1;i<top;i++)
printf(" %d",stack[i]);
puts("");
}
void dfs()
{
if(top==n)
{
if(prime[stack[0]+stack[top-1]])
print();
return;
}
int i;
for(i=2;i<=n;i++)
if(!mark[i]&&prime[stack[top-1]+i])
{
mark[i]=1;
stack[top++]=i;
dfs();
top--;
mark[i]=0;
}
}
int main()
{
while(~scanf("%d",&n))
{
mark[1]=1;
stack[top++]=1;
dfs();
}
return 0;
}
