从 1 ∼ n 1∼n 这 n n 个数，摆成一个环，要求相邻的两个数的和是素数，按照由小到大请输出所有可能的摆放形式。

### 解决方案 为了实现将1到n的数字排列成环，使得每对相邻数字之和为素数的目标，可以采用回溯算法来尝试所有可能的排列组合，并验证这些条件。 #### 1. 判断素数函数 首先定义一个辅助函数用于判断给定整数是否为素数： ```python def is_prime(num): if num <= 1: return False for i in range(2, int(num ** 0.5) + 1): if num % i == 0: return False return True ``` 此部分代码实现了基本的素数检测逻辑[^3]。 #### 2. 回溯法构建符合条件的圆圈序列 接下来编写核心递归函数`find_circle`来进行搜索并记录满足条件的结果列表： ```python from itertools import permutations def find_circles(n): nums = list(range(1, n + 1)) def backtrack(path): # 如果路径长度等于目标数量，则完成一轮完整的循环检查 if len(path) == n and is_prime(path[-1] + path[0]): result.append(list(path)) return used = set() for next_num in nums: if (next_num not in path and ((not path or is_prime(next_num + path[-1])))): if next_num in used: continue used.add(next_num) path.append(next_num) backtrack(path) path.pop() result = [] backtrack([]) return result ``` 上述方法通过迭代器生成全排列并通过剪枝优化减少不必要的计算开销。当发现当前节点无法继续扩展时立即返回上一层继续探索其他分支直到遍历完毕全部可能性空间为止[^4]。 #### 3. 测试案例展示 最后提供几个简单的测试用例帮助理解该算法的工作原理： ```python if __name__ == "__main__": test_cases = [4, 6] for case in test_cases: circles = find_circles(case) print(f"Circular arrangements with {case} elements:") for circle in circles: formatted_output = " -> ".join(map(str, circle)) + f" -> {circle[0]}" print(formatted_output) ``` 这段程序会输出指定范围内所有的合法圆形布局形式供观察分析[^5]。