素数环

试题描述

    输入正整数n，用整数1，2，3，……，n 的某种排列组成一个环，使任意相邻的两数和均为素数。你的任务是输出有多少种排列方案。

输入

一个正整数n。

输出

一个数，代表有多少种方案。

输入示例

6

输出示例

2

其他说明

n〈=16

用搜索。

#include <iostream>

using namespace std;
int A[21],vis[21],n,t;  //A数组储存的是符合的素数环，vis判断当前数字是否访问过（visit） 

bool is_prime(int n)   //判断素数标准模板
{
    for(int i=2;i*i<=n;i++) if(n%i==0) return false;
    return true;
}

void js(int x)
{
    if(x==n && is_prime(A[0]+A[n-1])) t++;
    for(int i=2;i<=n;i++)  //从2开始一个个判断 
    {
        if(vis[i]==0 && is_prime(i+A[x-1])) //如果没有被用过且与其相邻数的和是素数 
        {
            A[x]=i;
            vis[i]=1;
            js(x+1);  //开始找下一个方案 
            vis[i]=0;  //在下一个方案中，这个位置并没有访问过，所以一定要标记回0 
        }
    }
}

int main()
{
    scanf("%d",&n);
    A[0]=1;
    vis[1]=1;
    js(1);
    printf("%d",t);
    //system("pause");
    return 0;
}