# 14053: 【原4053】Prime Ring

### 题目描述

author: 肖云轩 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4053

## Description

• -2-3-4-1- 请输出为 1 2 3 4
• -3-2-1-4- 请输出为 1 4 3 2

## Output Format

1-k行，按字典序输出k个答案，使用空格间隔N个数字

## Sample Input

``````4
``````

## Sample Output

``````1 2 3 4
1 4 3 2
``````

## 数据范围

``````对于40%的数据 (2 <= N < 10)

``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

bool notPrime[] = {0, 0, 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};

int nums[20];
bool vis[20];
bool flag;
int N;

void search(int current) {
if (current == N) {
if (notPrime[nums[0] + nums[N - 1]]) {
for (int i = 0; i < N; ++i) {
printf("%d ", nums[i]);
}
printf("\n");
flag = true;
}
} else {
for (int i = 2; i <= N; ++i) {
if (!vis[i] && notPrime[i + nums[current - 1]]) {
nums[current] = i;
vis[i] = true;
search(current + 1);
vis[i] = false;
}
}
}
}

int main() {
cin >> N;
if (N % 2 == 1) {
printf("None\n");
return 0;
}

for (int i = 1; i <= N; ++i) {
nums[i - 1] = i;
}

search(1);
if (!flag) {
printf("None\n");
}

return 0;
}
``````

## FineArtz's solution

``````/* Prime Ring */
#include <iostream>
#include <cmath>
using namespace std;

bool canplace[17][17];
bool beplaced[17];
int a[20];
int n;

bool isp(int x){
if (x == 2) return true;
for (int i = 2; i <= trunc(sqrt(x)) + 1; ++i)
if (x % i == 0) return false;
return true;
}
bool check(int a[], int n){
for (int i = 0; i <= n - 1; ++i)
if (!isp(a[i] + a[i + 1])) return false;
return true;
}

void dfs(int x){
if (x == n + 1){
for (int i = 1; i <= n; ++i)
cout << a[i] << ' ';
cout << '\n';
return;
}
for (int i = 2 - x % 2; i <= n; i += 2){
if (!beplaced[i] && canplace[i][a[x - 1]]){
if (x == n && !canplace[i][1]) continue;
beplaced[i] = true;
a[x] = i;
dfs(x + 1);
a[x] = 0;
beplaced[i] = false;
}
}
}
int main(){
cin >> n;
if (n % 2 != 0){
cout << "None" << endl;
}
for (int i = 2; i <= n; ++i)
for (int j = 1; j < i; ++j){
if (isp(i + j)) canplace[i][j] = true;
else canplace[i][j] = false;
canplace[j][i] = canplace[i][j];
}
a[1] = 1;
beplaced[1] = true;
dfs(2);
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

bool not_num[50] = { 0 };
struct edge {
int num = 0;
int to[20] = { 0 };

to[num++] = pos;
}
};
edge edges[20];
bool visited[20] = { 0 };
int route[20] = { 0 };
int n;
int cnt = 0;

void DFS(int num, int pos) {
if (num == 0) {
if (pos == 1) {
++cnt;
printf("%d", route[0]);
for (int i = 1; i < n; ++i)
printf(" %d", route[i]);
printf("\n");
}
return;
}
if (visited[pos])
return;
visited[pos] = true;
route[n - num] = pos;
for (int i = 0; i < edges[pos].num; ++i) {
DFS(num - 1, edges[pos].to[i]);
}
visited[pos] = false;
route[n - num] = 0;
}

int main() {
//计算质数
int max_k = 40;
for (int i = 2; i <= max_k / 2 + 1; ++i) {
if (not_num[i])
continue;
for (int j = i * 2; j <= max_k; j += i)
not_num[j] = true;
}

cin >> n;

//计算质数路径
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j)
continue;
if (!not_num[i + j])
}
}

DFS(n, 1);
if (cnt == 0)
printf("None");

return 0;
}
``````

## q4x3's solution

``````/**
* dfs
**/
#include <stdio.h>
#include <iostream>

using namespace std;

int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

bool isPrime(int a) {
for(int i = 0;i < 11;++ i) {
if(a == p[i]) return 1;
}
return 0;
}

int n, a[20], vis[20];

void dfs(int x) {
if(x == n + 1 && isPrime(a[1] + a[n])) {
for(int i = 1;i <= n;++ i) {
printf("%d ", a[i]);
}
printf("\n");
return;
}
for(int i = 2;i <= n;++ i) {
if(!vis[i] && isPrime(a[x - 1] + i)) {
vis[i] = 1;
a[x] = i;
dfs(x + 1);
vis[i] = 0;
}
}
}

int main() {
cin >> n;
if((n == 1) || (n == 3) || (n == 5) || (n == 7) || (n == 9) || (n == 11)|| (n == 13) || (n == 15)) {
cout << "None" << endl;
} else {
a[1] = 1;
dfs(2);
}
return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int rec[20];
int _is_prime[1000] = { 0 };
bool used[20] = { 0 };
int N;

bool is_prime(int i) {
if (_is_prime[i] == 0) {
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
_is_prime[i] = 2;
return false;
}
}
_is_prime[i] = 1;
return true;
} else {
return _is_prime[i] == 1;
}
}

bool found = false;
int dfs(int n) {
if (n > N) {
if (is_prime(rec[N] + rec[1])) {
found = true;
for (int i = 1; i <= N; i++) printf("%d ", rec[i]);
printf("\n");
}
return 1;
}
for (int i = 1; i <= N; i++) {
if (!used[i]) {
if (is_prime(rec[n - 1] + i)) {
rec[n] = i;
used[i] = true;
dfs(n + 1);
used[i] = false;
}
}
}
return 0;
}

int main() {
cin >> N;
used[1] = true;
rec[1] = 1;
dfs(2);
if (!found) cout << "None" << endl;
return 0;
}
``````

## victrid's solution

``````#include <cstring>
#include <iostream>
using namespace std;
//Is the cout's problem?
//下次再不printf我直播吃屎
bool sum_is_prime[17][17] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 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, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,
0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0};

bool visited[17] = {0};
int storage[17]  = {0};
bool gotcha      = false;
int dfs(int num, int depth, int total) {
depth += 1;
visited[num]   = true;
storage[depth] = num;
if (depth == total) {
if (sum_is_prime[1][num]) {
for (int i = 1; i <= depth; i++) {
printf("%d ", storage[i]);
}
printf("\n");
gotcha = true;
} else {
visited[num] = false;
return 0;
}
}
for (int i = 2 + (num & 1) ^ 1; i <= total; i += 2)
if (sum_is_prime[num][i] && (!visited[i]))
dfs(i, depth, total);
visited[num] = false;
return 0;
}
int main() {
int total;
cin >> total;
if (total & 1) {
cout << "None" << endl;
return 0;
}
dfs(1, 0, total);
if (!gotcha)
cout << "None" << endl;
return 0;
}
``````