求解素数环问题

素数环问题是一种经典的组合数学问题，其描述如下：

给定一个正整数 n，找到长度为 n 的环形排列，使得相邻两个数之和均为素数。同一个数字不能被重复使用。

解决素数环问题的一种常见方法是使用回溯法。具体地，我们可以定义一个长度为 n 的数组 arr，表示当前已经排列好的数字序列。我们从数字 1 开始，依次尝试将它放到 arr[0] 的位置，然后递归搜索下一个数字。如果当前数字无法满足相邻两个数之和为素数的条件，我们就回溯到上一个数字，继续尝试下一个可行的位置。

为了判断两个数字之和是否为素数，我们可以使用一个预处理表格，将所有可能的素数先计算出来，然后在回溯过程中直接查表即可。

下面是一个简单的 Python 代码实现：

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def solve_prime_ring(n):
    arr = [0] * n
    primes = [i for i in range(2, 2 * n) if is_prime(i)]
    
    def backtrack(k):
        if k == n:
            if is_prime(arr[0] + arr[n-1]):
                print(arr)
            return
        for i in range(1, n):
            if i not in arr and is_prime(i + arr[k-1]):
                arr[k] = i
                backtrack(k+1)
                arr[k] = 0
    
    arr[0] = 1
    backtrack(1)

solve_prime_ring(5)

这里的 is_prime 函数用来判断一个数是否为素数，primes 则是一个预处理的素数表格。在回溯函数 backtrack 中，我们依次尝试将数字 1 到 n-1 放到 arr[k] 的位置，只有当该数字还未被使用且与前一个数字之和为素数时，才递归搜索下一个数字。当搜索到第 n 个数字时，如果第一个数字与最后一个数字之和为素数，则打印出当前符合要求的排列，否则回溯到上一个数字继续尝试。最终，程序会输出所有符合条件的素数环。