【例5.1】素数环

GitHub跳转原题关系图返回列表

用奇偶性先判定奇数 n 无解,偶数 n 固定起点 1 后 DFS 回溯,靠相邻和的素数剪枝找到任意一组解。

OJ: roj

题目 ID: 2110

难度:普及-

标签:搜索回溯python

创建: 2026-10-08 07:30

更新: 2026-10-08 07:30

形式化题目

给定整数 nn(4⩽n⩽304 \leqslant n \leqslant 30),求一个 1,2,…,n1, 2, \dots, n 的排列 a0,a1,…,an−1a_0, a_1, \dots, a_{n-1},使得它首尾相接后环上每对相邻数之和都是素数,即

ai+a(i+1) mod n 为素数(0⩽i<n). a_i + a_{(i+1) \bmod n} \text{ 为素数} \qquad (0 \leqslant i < n).

由于条件只依赖相邻关系,{ai}\{a_i\} 本身只确定"环"的形态:整体旋转或反向都不改变 一个环是否合法。因此只需输出任意一组解序(排列),不要求特定的起点或方向。

正解

思路

第一步:先用奇偶性判定什么时候无解。

n⩾4n \geqslant 4,环上相邻两数之和最小是 1+2=31 + 2 = 3,不可能是素数 22; 所以所有相邻和都是奇素数。两个整数之和为奇数,当且仅当它们一奇一偶, 于是环上相邻两数必须始终一奇一偶,也就是奇偶交替。

奇偶交替的环要求奇数个数与偶数个数相等。而 1…n1 \dots n 中奇数比偶数多一个 (nn 为奇数时),环上必然出现一对"奇 + 奇",其和为偶数且大于 22,不是素数。 所以:

  • nn 为奇数:一定无解,不需要搜索;
  • nn 为偶数(4⩽n⩽304 \leqslant n \leqslant 30):都有解(随仓数据 10 个点验证)。

这一步不只是"优化":若跳过它直接穷举,n=29n = 29 这类奇数点会在指数级的死分支上 长时间搜索,所以它同时是正确性(无解时输出为空)与可行性(不超时)的一部分。

第二步:破掉环的旋转对称。

数字 11 一定在环中,把 a0a_0 固定为 11 不会漏解——任何合法环旋转一下都能让 11 落到第 00 位。这样只需构造一条"以 11 开头的素数链",再把尾首和补上检验即可。

第三步:DFS 回溯 + 即时剪枝。

按位置 0,1,…,n−10, 1, \dots, n-1 依次填数,状态是"已填好的前缀 + 已用数字集合"。每当想把 候选值 vv 放到第 ii 位时,立刻检查 ai−1+va_{i-1} + v 是否为素数:不是素数就说明这条 分支已经不可能补成合法环,直接剪枝,不必等到填满 nn 个数才回退。因为素数在自然数中 分布稀疏,这层即时判定会在极浅的深度就砍掉绝大多数分支,实际搜索树极小。

递归的出口不是"填满就成功",而要把最后一个数和 a0a_0 之和也检查一遍:这一步很容易漏。 找到第一组解后让递归层层返回 true,避免继续搜索整棵树。

最后,输出时把起点 11 挪到末尾(输出 a1,a2,…,an−1,a0a_1, a_2, \dots, a_{n-1}, a_0)。这只是同一个环 的另一种读法,恰好能让 n=6n = 6 的输出逐字节等于题面样例 4 3 2 5 6 1。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:30
# update_at: 2026-10-08 07:30

import sys

MAX_N = 30                # 题面上限 n <= 30
MAX_SUM = 2 * MAX_N - 1   # 相邻两数之和的上界 n + (n-1) = 59

# ISPRIME[s]:相邻两数之和 s 是否为素数,下标即和本身;59 以内试除足够快
ISPRIME: list[bool] = [s > 1 and all(s % d for d in range(2, int(s ** 0.5) + 1))
                       for s in range(MAX_SUM + 1)]  # 素数表 60 项


def find_ring(n: int) -> list[int] | None:
    """找一条以 1 开头、候选递增的首个素数链;无解返回 None。

    n 为奇数时无解:n >= 4 的相邻和都是奇素数,故环上相邻两数必须一奇一偶、
    奇偶交替,而奇数 n 的 1..n 中奇数比偶数多一个,必有"奇+奇"相邻,和为偶且 > 2。
    """
    if n % 2:
        return None

    path = [1]  # 固定起点为 1,破掉环的旋转对称
    used = [False] * (n + 1)
    used[1] = True

    def dfs() -> bool:
        """在链尾接一个未用过的数,使相邻和为素数;能否接成完整素数环。"""
        if len(path) == n:
            return ISPRIME[path[-1] + path[0]]  # 只剩尾首闭合这一对要检查
        for v in range(2, n + 1):
            can_place = not used[v] and ISPRIME[path[-1] + v]
            if not can_place:
                continue
            used[v] = True
            path.append(v)
            if dfs():  # 只要任意一组解,成功信号层层上传
                return True
            path.pop()  # 失败回溯:撤销 v
            used[v] = False
        return False

    return path[:] if dfs() else None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, 0)
    ring = find_ring(n) if 1 <= n <= MAX_N else None
    if ring is None:
        return  # 奇数 n 无解:与数据约定一致,输出为空
    # 输出时把起点 1 挪到末尾:环无起点,等价读法,与题面样例 `4 3 2 5 6 1` 一致
    print(*ring[1:] + ring[:1])


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:30
 * update_at: 2026-10-08 07:30
 */
// 一本通 2110《【例5.1】素数环》
// 题意:把 1..n 排成一个环,使相邻两数之和(含首尾这一对)均为素数,输出任意一组解。
// 数据范围:4 <= n <= 30,time 1000 ms / memory 64 MB。
//
// 关键结论(先判有无解,再搜索):
//   n >= 4 时相邻两数之和至少为 1+2=3,不可能是素数 2,故相邻和都是奇素数,
//   于是环上每对相邻数必须一奇一偶 => 环上奇偶必须交替。
//   n 为奇数时 1..n 中奇数比偶数多一个,环上必然出现"奇+奇",其和为偶数且 > 2,
//   不是素数 => 奇数 n 无解。偶数 n(n=4..30)都有解(本地逐点实测)。
//   正因如此先对奇数直接空输出,否则 n=29 的穷举会指数级变慢。
// 偶数 n 用 DFS 回溯:固定 a0=1 破掉"环的旋转对称",候选值递增枚举,
//   每放一个数就立即判定相邻和是否为素数,找到第一组解就层层返回。
#include <cstdio>

typedef long long ll;

const int MAXN = 30;           // 题面上限 n <= 30
const int PMAX = 2 * MAXN + 1; // 相邻两数之和最大为 n+(n-1) = 59

bool is_prime[PMAX + 1];       // is_prime[s]:相邻两数之和 s 是否为素数
bool used[MAXN + 1];           // used[v]:数字 v 是否已经放进环里
int ring[MAXN];                // ring[0..n-1]:以 1 开头的素数链
ll n;                          // 输入的环长

// 埃氏筛:预处理 0..PMAX 的素数标记,使相邻和判定变成 O(1)
void build_prime_table() {
    for (int s = 0; s <= PMAX; ++s) is_prime[s] = true;
    is_prime[0] = false;
    is_prime[1] = false;
    for (int p = 2; p * p <= PMAX; ++p) {
        if (!is_prime[p]) continue;
        for (int s = p * p; s <= PMAX; s += p) is_prime[s] = false;
    }
}

// ring[0..len-1] 已填好且链上相邻和均为素数,尝试填第 len 个位置;
// 找到一个完整素数环返回 true。len 从 1 开始(ring[0]=1 已固定)。
bool dfs(int len) {
    if (len == n) return is_prime[ring[len - 1] + ring[0]]; // 只剩尾首闭合要检查
    for (int v = 2; v <= n; ++v) {
        if (used[v]) continue;
        if (!is_prime[ring[len - 1] + v]) continue; // 相邻和不是素数,当前分支已死,剪枝
        used[v] = true;
        ring[len] = v;
        if (dfs(len + 1)) return true; // 只要任意一组解,成功信号层层上传
        used[v] = false;               // 失败回溯:撤销 v 的占用
    }
    return false;
}

int main() {
    if (scanf("%lld", &n) != 1) return 0;
    if (n < 1) return 0;           // 题面范围外,防御性退出
    if (n > MAXN) return 0;        // 数组按题面上限静态开,超范围直接退出
    build_prime_table();
    if (n % 2 != 0) return 0;      // 奇数 n 无解:数据约定无解时输出为空,不打印任何内容

    ring[0] = 1;                   // 固定起点消除旋转重复
    used[1] = true;
    if (!dfs(1)) return 0;

    // 输出时把起点 1 挪到末尾:环没有起点,这是同一个环的另一种读法,
    // 与题面样例 `4 3 2 5 6 1`(n=6)以及随仓数据的读法一致。
    for (int i = 1; i < n; ++i) printf("%d ", ring[i]);
    printf("%d\n", ring[0]);
    return 0;
}

复杂度

  • 时间:最坏理论上界仍是 O(n!)O(n!),但奇偶约束加上"相邻和是素数"的即时剪枝把有效状态 压缩到常数级,n⩽30n \leqslant 30 时找到首解只需几十个搜索结点,远小于 1000 ms。
  • 空间:递归深度 O(n)O(n),used / ring 数组 O(n)O(n),素数表 O(n)O(n),总计 O(n)O(n)。

总结

  • 核心观察是奇偶性:n⩾4n \geqslant 4 的相邻和只可能是奇素数,所以环必须奇偶交替, 奇数 nn 直接无解。
  • 有解时用"固定起点 + 即时素数剪枝 + 找到即返回"的 DFS,规模小到可以直接搜索。
  • 两个易错点:末位与首位的闭合检查、以及失败分支必须恢复 used[v]。
  • 数据与无解约定:随仓素材里带数据生成脚本 data.py,说明 data/ 是自造数据 而非官方数据,题面也可能来自网络重建,与官方原题的出题意图可能有偏差。其 10 个点覆盖 n=4,5,6,8,10,14,20,26,29,30n = 4, 5, 6, 8, 10, 14, 20, 26, 29, 30,其中 n=5,29n = 5, 29 为奇数(无解),其 .out 是 0 字节空文件——即数据发布方对"无解"的约定是不输出任何内容,而不是输出 -1 或提示文字,本题解遵循该约定。另外 std.cpp 用"固定末位为 1、首位从 2 起递增" 的搜索序,本题解用"固定首位为 1、候选递增",输出的是同一个环的不同读法;已实测两者 对这 10 个点(含样例)逐字节一致,故与随仓 data/ 完全兼容。