素数环

coding>C++
1.1k 词

题目描述

不过有些水题可能看着简单，但是实现起来还是挺麻烦的，要注意很多边边角角的细节，稍不留神就会WA。

给定 n $(n<=20)$ 把 1~n的n个数组成一个环，使得相邻的两个数和都是素数，如果不存在输出no solution

输入

一个n $(2<=n<=20)$

输出

输出这n个数 ，使得相邻的两个数都是素数，如果不存在输出no solution

样例输入

1
4

样例输出

1
1 2 3 4

提示

如果存在多组，请输出字典序最小的那个

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
bool Flag=false;
bool Index[21];
bool flag[40];
int ans[21];
bool Prime(int n)
{
    if(n<2)
        return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
void DFS(int cnt,int n) {
    if(Flag)
        return;
    if(cnt==n&&flag[ans[cnt-1]+ans[0]]) {
        for(int i=0; i<cnt; i++)
            cout<<ans[i]<<" ";
        Flag=true;
    }
    for(int i=1; i<=n; i++) {
        if(!Index[i]&&flag[i+ans[cnt-1]]) {
            ans[cnt]=i;
            Index[i]=true;
            DFS(cnt+1,n);
            Index[i]=false;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    fill(Index,Index+21,false);
    fill(flag,flag+40,false);
    for(int i=1; i<40; i++) flag[i]=Prime(i);
    ans[0]=1;
    Index[1]=true;
    if (n%2==0) DFS(1,n);
    if(!Flag) cout<<"no solution"<<endl;
    return 0;
}