1. 问题描述
素数环问题，也叫 Prime Ring Problem。
给定正整数 ，要求将 到 这 个数字排成一个环，使得任意两个相邻数字之和都是素数。
例如，当 时，一个合法的素数环为：
因为：
这些和全部都是素数。
注意，最后一个数和第一个数也是相邻的，因为它们组成的是一个环。
2. 算法策略
素数环问题使用：
回溯法可以理解为一种深度优先搜索，核心思想是：
能继续就继续往下搜索，走不通就退回来，换一个选择再试。
素数环问题是在 到 的所有排列中，寻找满足条件的排列。如果直接枚举所有排列，复杂度很高。例如 时，排列总数为：
但实际上，很多排列刚排到一半就已经不可能成为答案。例如：
因为：
不是素数，所以后面无论怎么排，都不可能形成合法素数环。
这时候就可以直接剪枝。
3. 数学性质：奇偶性约束
素数环问题有一个很重要的性质：相邻数字必须一奇一偶。因为除了 之外，所有素数都是奇数。
两个整数相加时：
| 情况 | 结果 |
|---|---|
| 奇数 + 奇数 | 偶数 |
| 偶数 + 偶数 | 偶数 |
| 奇数 + 偶数 | 奇数 |
在素数环中，相邻两个数的和最小是 ，因此和不可能是 。所以相邻两个数的和如果是素数，就只能是奇数，两个数字也就必须一奇一偶。因此，整个环必须满足：
交替排列。
这也说明：当 且 为奇数时，素数环无解，因为 到 中奇数和偶数数量不相等，无法形成完整的奇偶交替闭环。
4. 固定第一个数为 1
素数环是一个环，所以旋转后本质上还是同一个环。例如：
和：
其实表示的是同一个环，只是起点不同。
为了避免这种旋转重复，通常固定第一个位置为：
这样可以减少重复答案，也可以缩小搜索空间。
5. 解空间与排列树
可以用数组表示当前排列：
其中：
其余位置从没有使用过的数字中选择，并要求相邻两数之和为素数，且最后一个数与第一个数之和也为素数。
因为每一层都要从剩余数字中选择一个数，所以解空间是一棵排列树。
以 为例：
第 1 层：固定 1第 2 层：从 2 到 8 中选择一个数第 3 层：继续从未使用的数字中选择一个数……第 8 层：形成完整排列搜索过程中不是所有分支都会继续展开。如果新加入的数字和前一个数字之和不是素数，就直接剪枝。
6. 剪枝条件
素数环问题主要有两个剪枝条件。
6.1 相邻和不是素数，直接剪枝
每放入一个新数字 ，都要检查：
是否为素数。
如果不是素数，当前分支直接结束。例如：
因为：
不是素数，所以这一支不需要继续搜索。
6.2 填满后检查首尾
由于这是一个环，所以当所有数字都放完后，还要检查最后一个数字和第一个数字的和：
是否为素数。
只有首尾也满足条件，才是一个完整的素数环。
7. 算法步骤
- 输入正整数 。
- 如果 且 为奇数，直接判断无解。
- 预处理 范围内的素数表。
- 定义数组
path保存当前排列。 - 定义数组
visited标记数字是否已经使用。 - 固定
path[0] = 1。 - 从第二个位置开始回溯搜索。
- 每次尝试放入一个未使用的数字。
- 如果它与前一个数字之和是素数，则继续递归。
- 如果不满足条件，则剪枝。
- 当所有位置填满时，检查最后一个数和第一个数之和是否为素数。
- 如果满足，输出当前排列。
8. 以 n = 8 为例
固定第一个数为：
第二个数必须满足：
是素数。
所以可以选择：
因为：
都是素数。
而：
都不是素数，所以这些分支直接剪掉。
当 时，固定 在首位，可以得到 4 个素数环：
1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 29. Java 实现
import java.util.Arrays;
public class PrimeRing {
private static int n; private static int[] path; // 存储当前排列 private static boolean[] visited; // 标记数字是否已经使用 private static boolean[] isPrime; // 素数表
public static void main(String[] args) { int inputN = 8;
System.out.println("n = " + inputN + " 时的素数环结果："); solvePrimeRing(inputN); }
public static void solvePrimeRing(int inputN) { n = inputN;
// 如果 n > 1 且 n 是奇数，则无法形成奇偶交替的闭环 if (n > 1 && n % 2 == 1) { System.out.println("无解"); return; }
path = new int[n]; // 下标直接对应数字，避免出现“差一错误” visited = new boolean[n + 1];
// 相邻两数之和最大为 2n precomputePrimes(2 * n);
// 固定第一个数为 1，避免旋转重复 path[0] = 1; visited[1] = true;
// 从下标 1 开始填数 backtrack(1); }
private static void backtrack(int index) { // 已经填满 n 个数 if (index == n) { // 检查最后一个数和第一个数之和是否为素数 if (isPrime[path[n - 1] + path[0]]) { printPath(); } return; }
// 从 2 到 n 尝试放入未使用的数字 for (int i = 2; i <= n; i++) { // 当前数字没有使用过，并且与前一个数字之和为素数 if (!visited[i] && isPrime[path[index - 1] + i]) { path[index] = i; visited[i] = true;
backtrack(index + 1);
// 回溯：撤销选择 visited[i] = false; } } }
private static void precomputePrimes(int max) { isPrime = new boolean[max + 1]; Arrays.fill(isPrime, true);
if (max >= 0) { isPrime[0] = false; }
if (max >= 1) { isPrime[1] = false; }
for (int p = 2; p * p <= max; p++) { if (isPrime[p]) { for (int i = p * p; i <= max; i += p) { isPrime[i] = false; } } } }
private static void printPath() { for (int i = 0; i < n; i++) { System.out.print(path[i]);
if (i != n - 1) { System.out.print(" "); } }
System.out.println(); }}运行结果：
n = 8 时的素数环结果：1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 210. 代码解释
10.1 path 数组
private static int[] path;path 用来保存当前已经构造出的排列。
例如：
1 2 3表示当前已经放好了前三个数字。
10.2 visited 数组
private static boolean[] visited;visited[i] 表示数字 i 是否已经被使用。
这里把 visited 的大小定义为 n + 1，是为了让数字和数组下标一一对应。比如数字 6 就直接用 visited[6] 表示，而不需要写成 visited[5]。这样虽然空出了 visited[0]，但可以减少下标偏移带来的差一错误。
如果：
visited[3] = true;表示数字 3 已经在当前排列中，后面不能重复使用。
10.3 isPrime 数组
private static boolean[] isPrime;isPrime[x] 表示数字 x 是否是素数。
例如：
isPrime[7] = true;isPrime[8] = false;因为 是素数， 不是素数。
10.4 埃拉托斯特尼筛法
代码中的 precomputePrimes 使用的是埃拉托斯特尼筛法，简称“埃氏筛”。
它的作用是：在回溯开始前，先把 到 max 范围内的素数全部算出来，保存到 isPrime 数组中。之后判断相邻和是否为素数时，只需要查表：
isPrime[sum]时间复杂度就是 。
埃氏筛的思路是：先假设所有大于等于 的数都是素数，然后从小到大枚举每个数。如果当前数 仍然是素数，就把它的倍数标记为非素数。
以 max = 10 为例：
| 步骤 | 操作 | 剩下仍可能是素数的数 |
|---|---|---|
| 初始化 | 排除 和 | |
| 筛掉 | ||
| 筛掉 |
最终留下来的 ，就是 以内的素数。
代码中内层循环从：
int i = p * p;开始，而不是从 2 * p 开始，是因为更小的倍数已经被前面的数筛过了。比如枚举到 时， 已经在 的时候被筛掉了，所以直接从 开始即可。
外层循环条件是：
p * p <= max原因是：如果一个数 是合数，那么它一定可以写成 ，其中至少有一个因数不超过 。所以只要筛到 ，就足够把 max 以内的合数全部筛掉。
在素数环问题中，相邻两个数的最大和是：
为了写起来更方便，代码直接预处理到 2 * n，之后判断某个和是否为素数时，只需要访问：
isPrime[path[index - 1] + i]空间换时间埃氏筛会多用一个
isPrime数组，但能把回溯过程中的素数判断变成查表。回溯会反复尝试很多组合，这种预处理通常很划算。
10.5 回溯函数
private static void backtrack(int index)index 表示当前要填写的位置。
如果：
index == n说明所有位置都已经填完，需要检查首尾是否也满足素数条件。
如果还没有填完，就遍历所有还没使用过的数字，尝试放到当前位置。
10.6 回溯过程
核心代码是：
if (!visited[i] && isPrime[path[index - 1] + i]) { path[index] = i; visited[i] = true;
backtrack(index + 1);
visited[i] = false;}这段代码可以分成四步：
1. 判断数字 i 是否可以放入当前位置。2. 如果可以，就把 i 放入 path[index]。3. 递归搜索下一个位置。4. 搜索结束后撤销选择，尝试其他数字。其中 visited[i] = false; 就是回溯的关键，它表示当前分支搜索完了，把这个数字拿出来，换别的数字试试。
11. 复杂度分析
在最坏情况下，如果不考虑剪枝，需要枚举排列，复杂度接近：
因为第一个位置固定为 ，所以只需要排列剩下的 个数字。
但实际运行中，由于有“相邻和为素数”和“奇偶交替”两个强剪枝条件，搜索空间会大大减少。
空间复杂度主要来自：
path数组：visited数组：- 递归调用栈：
isPrime数组：
所以整体空间复杂度为：
12. 总结
素数环问题可以概括为：
全排列搜索 + 素数条件剪枝 + 首尾相连检查。
核心内容如下：
- 使用回溯法解决。
- 固定第一个数字为 ，避免旋转重复。
- 使用
visited数组避免重复使用数字。 - 每次加入新数字时，检查它和前一个数字之和是否为素数。
- 填满后，再检查最后一个数字和第一个数字之和是否为素数。
- 如果 且 为奇数，直接无解。
- 预处理素数表，可以把素数判断变成 。
口诀：
素数环问题就是在排列树上做回溯搜索，每一步用“相邻和为素数”进行剪枝。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时