/*问题描述：把从1到20这20数摆成一个环，要求相邻的两个数的和是一个素数。*/
#include<iostream>
#include<math.h>
using namespace std;
int a[21];
void output()
{
int i;
for(i=1;i<=20;i++)
cout<<a[i]<<" ";
cout<<endl;
}
int check1(int i, int n)//与前面的数不相同
{
int j;
for(j=1;j<=n-1;j++)
{
if(a[j]==i)
return 0;
}
return 1;
}
int check2(int n)//素数检查
{
int t=sqrt(n);
int j;
for(j=2;j<=t;j++)
{
if(n%j==0)
return 0;
}
return 1;
}
int check3(int i,int n) //检查相邻数字之和是否为素数
{
if(n<20)
return check2(i+a[n-1]);
else
{
int t=check2(i+a[n-1])+check2(i+a[1]);
if(t==2)
return 1;
else
return 0;
}
}
void find(int n)
{
int i;
for(i=2;i<=20;i++)
{
if(check1(i,n)==1&&check3(i,n)==1)
{
a[n]=i;
if(n==20)
output();
else
{
find(n+1);
a[n]=0;
}
}
}
}
int main()
{
int i;
for(i=1;i<=20;i++)
{
a[i]=0;
}
a[1]=1;
find(2);
return 0;
}