素数环

比眉伴天荒 2022-08-07 01:46 159阅读 0赞

## 素数环 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

![20120315192417_81102.gif][]

输入

有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。

输出

每组第一行输出对应的Case序号，从1开始。  
如果存在满足题意叙述的素数环，从小到大输出。  
否则输出No Answer。

样例输入

6
    8
    3
    0

样例输出

Case 1:
    1 4 3 2 5 6
    1 6 5 2 3 4
    Case 2:
    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
    Case 3:
    No Answer

\#include<stdio.h>  
  
  
\#define max 6  
  
  
int vis\[max\];  
int a\[max\];  
  
  
int is\_prime(int n) \{  
int i;  
for(i = 2 ; i \* i < n ;i++) \{  
if(n % i == 0)  
return 0;  
\}  
return 1;  
\}  
  
  
void dfs(int cur) \{  
if(cur == max && is\_prime(a\[0\] + a\[max - 1\]))\{  
for(int i = 0 ; i < max ;i++) \{  
printf("%d ",a\[i\]);  
\}  
printf("\\n");  
\}else  
for(int i = 2; i <= max ;i++) \{  
if(!vis\[i\] && is\_prime(i + a\[cur - 1\])) \{  
a\[cur\] = i;  
vis\[i\] = 1;  
dfs(cur + 1);  
vis\[i\] = 0;  
\}  
\}  
\}  
  
  
  
  
  
  
int main()\{  
a\[0\] = 1;  
dfs(1);  
scanf("%d");  
\}

[20120315192417_81102.gif]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20120315192417_81102.gif

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关 hduoj 1016 素数环 DFS +筛选法求素数

<table> <tbody> <tr> <td> <h2>Prime Ring Problem</h2> <strong>Time Limit: 4000/

素颜马尾好姑娘i/ 2024年02月18日 23:08/ 0 赞/ 48 阅读

相关素数环（深搜）

描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的

亦凉/ 2022年09月28日 13:01/ 0 赞/ 164 阅读

相关 NYOJ 488-素数环【dfs】

素数环时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都

古城微笑少年丶/ 2022年08月21日 11:57/ 0 赞/ 161 阅读

相关 hdoj 1016 Prime Ring Problem【素数环】

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/3276

痛定思痛。/ 2022年08月08日 15:58/ 0 赞/ 182 阅读

相关素数环（dfs）

素数环时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首

清疚/ 2022年08月07日 15:52/ 0 赞/ 209 阅读

相关素数环

素数环时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首

比眉伴天荒/ 2022年08月07日 01:46/ 0 赞/ 160 阅读

相关搜索算法之素数环

题目描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下图

ゝ一纸荒年。/ 2022年06月02日 03:52/ 0 赞/ 147 阅读

相关回溯法——素数环C++实现

本文共928个字，预计阅读时间需要3分钟。回溯法简介回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪

以你之姓@/ 2022年01月23日 03:35/ 0 赞/ 220 阅读

相关素数环问题

问题链接：[https://www.nowcoder.com/questionTerminal/4437f37768eb45fe9b79d88db47ff32a?orderBy

逃离我推掉我的手/ 2021年11月04日 23:04/ 0 赞/ 290 阅读

相关素数环

题目描述素数环:从1到n这n个数摆成一个环，要求相邻的两个数的和是一个素数。如，n=8是，素数环为： 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6

向右看齐/ 2021年09月28日 18:46/ 0 赞/ 344 阅读