质数

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

总和 S 的奇偶性把答案锁死在 -1/1/2/3 四种:S 为质数取 1,S 拆成两质数取 2,否则用哥德巴赫弱形式取 3,再用从大到小的贪心把目标和落到具体数上。

OJ: roj

题目 ID: 1800

难度:提高

标签:数学质数哥德巴赫猜想构造python

创建: 2026-10-08 03:54

更新: 2026-10-08 03:54

形式化题目

给定 nn,要把全集 U={1,2,…,n}U = \{1, 2, \dots, n\} 划分成 cntcnt 个两两不交的非空子集 A1,…,AcntA_1, \dots, A_{cnt},满足

⨆i=1cntAi=U,∑x∈Aix 是质数(1⩽i⩽cnt). \bigsqcup_{i=1}^{cnt} A_i = U, \qquad \sum_{x \in A_i} x \ \text{是质数} \quad (1 \leqslant i \leqslant cnt).

要求输出最小的 cntcnt,以及一个具体方案:第 ii 个数给出自然数 ii 所在的集合编号 (编号取值 [1,cnt][1, cnt],多解任意输出一个);无解输出 −1-1。

数据规模:30%30\% 的数据 n⩽20n \leqslant 20,100%100\% 的数据 n⩽6000n \leqslant 6000。

方案不唯一,只要 cntcnt 最小、每个集合内元素和都是质数,任意一种输出都算对 (属于 special judge)。以题面样例 n=8n = 8 为例,S=36S = 36 不是质数而 5+315 + 31 是两个质数, 所以 cnt=2cnt = 2;样例给出的划分是 {1,4,5,6,7}\{1,4,5,6,7\}(和 2323)与 {2,3,8}\{2,3,8\}(和 1313), 本题代码给出的划分是 {5}\{5\}(和 55)与 {1,2,3,4,6,7,8}\{1,2,3,4,6,7,8\}(和 3131),两种都合法。

正解

思路

先把"最少集合数"和"怎么凑出这些集合"拆成两件事,因为它们各自有非常不同的抓手。

第一步:答案 cntcnt 只有四种取值。 所有集合的元素和加起来恰好是全集总和 S=n(n+1)2S = \frac{n(n+1)}{2},所以 cntcnt 的候选值由 "SS 最少能写成几个质数之和"决定:

  • n=1n = 1 时 S=1S = 1。11 既不是质数,也没有别的数可以帮它凑,只能输出 −1-1。 这是唯一的无解情形。
  • SS 本身是质数时取 cnt=1cnt = 1,把 1∼n1 \sim n 全放进一个集合。S=n(n+1)2S = \frac{n(n+1)}{2} 是质数只发生在 n=2n = 2(S=3S = 3),其余 nn 试一下就知道。
  • 否则看 SS 能否写成两个质数之和。这里要分奇偶:
    • SS 为偶数:由哥德巴赫猜想(在本题 S⩽1.8×107S \leqslant 1.8 \times 10^7 的范围内已被完全 验证),任何大于 22 的偶数都等于两个质数之和,所以 cnt=2cnt = 2 必然可行。
    • SS 为奇数:两个整数和为奇数必须一奇一偶,而唯一的偶质数是 22,因此形式只能是 2+(S−2)2 + (S-2)。于是只要检查 S−2S - 2 是不是质数即可。
  • 上一条不成立时(SS 为奇数且 S−2S-2 为合数):S−3S - 3 是偶数,同样由哥德巴赫猜想 可以拆成两个质数 p1+p2=S−3p_1 + p_2 = S - 3,再加上质数 33 就有 p1+p2+3=Sp_1 + p_2 + 3 = S。 所以 cnt⩽3cnt \leqslant 3 恒成立。

这就把问题从"搜子集"变成了"数论判别 + 构造":答案只可能是 −1,1,2,3-1, 1, 2, 3, 而"答案最小"这件事由上面的推导直接保证——1 不行才试 2,2 不行才落到 3, 所以不需要在程序里枚举 cntcnt。

第二步:怎么把目标和摊到具体的数上。 确定 cntcnt 之后,问题变成:给定目标和 PP,从 1∼n1 \sim n 中挑一组数和恰好为 PP。 关键观察是 1∼n1 \sim n 是连续整数,此时从 nn 往 11 扫描的贪心一定成功:每到数 ii, 只要当前余量 R⩾iR \geqslant i 就取走 ii,否则跳过。因为前缀 {1,…,i}\{1, \dots, i\} 的和 i(i+1)2\frac{i(i+1)}{2} 始终不小于此时还能用的最大可取量,余量一定在第 ii 个数处被"填平", 不会出现差 11 凑不满的死角。于是构造只需 O(n)O(n) 一次扫描。

两个分支因此落地为:

  • cnt=2cnt = 2:先找一对质数 PP 与 S−PS - P(SS 偶时从最小的质数往上试即可命中; SS 奇时只能是 P=2P = 2)。把所有数默认放进集合 2,再用贪心把和为 PP 的那组挪进集合 1, 集合 2 的和自动是 S−PS - P。
  • cnt=3cnt = 3:枚举两个互不相同的质数 a,b⩽na, b \leqslant n 使 S−a−bS - a - b 仍为质数, 把 aa、bb 各单独成一个集合,剩下的数全塞进第三个集合,其和恰为 S−a−bS - a - b。 由哥德巴赫弱形式(任一大于 55 的整数可写成三个质数之和)知这样的 (a,b)(a, b) 存在, 代码里从最小的质数往上找即可。

代码

Python 短解法与 C++ 同阶:都是埃氏筛 O(Slog⁡log⁡S)O(S \log \log S) 加一趟 O(n)O(n) 构造。 Python 侧只用标准库,筛法用 bytearray 切片赋值把内层循环交给 C 实现。

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 03:54
# update_at: 2026-10-08 03:54

import sys
from collections.abc import Iterator


def primes_upto(limit: int) -> bytearray:
    """返回下标可查的质数表 is_prime[0..limit]:埃氏筛,第 i 项为 1 表示 i 是质数。"""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            is_prime[i * i:: i] = bytearray(len(range(i * i, limit + 1, i)))
    return is_prime


def greedy_pick(n: int, target: int) -> Iterator[int]:
    """从 n 往下贪心取数凑出 target:1..n 的连续整数一定能凑满任意不超过级数和的目标。"""
    rest = target
    for i in range(n, 0, -1):
        if rest <= 0:
            return
        if i <= rest:          # 余量还装得下 i,就取走 i
            yield i
            rest -= i


def plan_sets(n: int, S: int, is_prime: bytearray) -> tuple[int, list[int]]:
    """按"S 需要几个质数相加"给出最少集合数与方案;答案只会是 1、2、3。"""
    if is_prime[S]:            # S 自身是质数:全部数字放一个集合
        return 1, [1] * (n + 1)

    # 取最小的质数 x 使 x 与 S-x 都是质数,则只拆两个集合:集合 1 凑出和 x
    two = next((x for x in range(2, S // 2 + 1) if is_prime[x] and is_prime[S - x]), None)
    if two is not None:
        group = [2] * (n + 1)
        for i in greedy_pick(n, two):
            group[i] = 1
        return 2, group

    # 否则 S 是奇数且 S-2 是合数:挑两个不同质数 a、b 单列,其余数之和 S-a-b 仍是质数
    prime_list = [i for i in range(2, n + 1) if is_prime[i]]
    a, b = next(
        (a, b)
        for a in prime_list
        for b in prime_list
        if a != b and is_prime[S - a - b]
    )
    group = [3] * (n + 1)      # 集合 3 = 其余全部数,和为 S-a-b,是质数
    group[a] = 1               # 集合 1 = {a}
    group[b] = 2               # 集合 2 = {b}
    return 3, group


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    if n == 1:                 # S = 1 既不是质数也无法再拆,唯一无解情形
        print(-1)
        return

    S = n * (n + 1) // 2
    cnt, group = plan_sets(n, S, primes_upto(S))
    print(cnt)
    print(' '.join(map(str, group[1:])))


if __name__ == "__main__":
    solve()

C++ 版本把筛表、质数表和归属数组都放在全局,避免大数组压栈; SS 上界 1800300018003000 用 long long 参与乘法,避免中途溢出。

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 03:54
 * update_at: 2026-10-08 03:54
 */
// main.cpp:把 1..n 分成尽量少的集合,使每个集合的元素和都是质数。
// 记 S = n(n+1)/2。答案只可能是 -1(n=1)、1(S 为质数)、2(S 拆成两质数之和)
// 或 3(S 为奇数且 S-2 为合数时拆成 3 个质数之和,用哥德巴赫猜想的弱形式兜底)。
// 集合的构造用"从 n 往下贪心凑和",因为 1..n 的连续整数一定能凑出任意不超过 S 的目标和。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 6000;         // 题面 n 的上限
const ll MAXS = 18003000;      // S 的上限:6000*6001/2
const int MAXP = 800;          // 不超过 6000 的质数个数(实际 783)

char comp[MAXS + 1];           // comp[x] = 1 表示 x 是合数(或 0/1),值域只有 0/1 用 char 省内存
int primeList[MAXP + 1];       // 不超过 n 的质数,升序
int primeCnt;
int belong[MAXN + 1];          // belong[i] = 自然数 i 所属的集合编号(1 起)

ll sum_all;                    // S = n(n+1)/2

// 埃氏筛,标记 [0, sum_all] 内的合数
void build_sieve() {
    comp[0] = comp[1] = 1;
    for (ll i = 2; i * i <= sum_all; i++) {
        if (comp[i]) continue;
        for (ll j = i * i; j <= sum_all; j += i) comp[j] = 1;
    }
}

// 收集不超过 n 的质数,供 cnt=3 分支挑 a、b 用
void build_primes(int n) {
    primeCnt = 0;
    for (int i = 2; i <= n; i++)
        if (!comp[i]) primeList[++primeCnt] = i;
}

// 从 n 往下贪心,把和为 target 的一组数标成集合 1;剩余的数保持集合 2
void greedy_split(int n, ll target) {
    ll rest = target;
    for (int i = n; i >= 1 && rest > 0; i--) {
        if (i <= rest) {           // 余量还装得下 i,就取走 i
            belong[i] = 1;
            rest -= i;
        }
    }
}

// 按题面格式输出归属数组,集合编号空间 [1, cnt]
void output(int n, int cnt) {
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++) printf("%d%c", belong[i], i == n ? '\n' : ' ');
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    if (n == 1) {                  // S = 1 既不是质数也无法再拆,唯一无解情形
        printf("-1\n");
        return 0;
    }

    sum_all = (ll)n * (n + 1) / 2;
    build_sieve();

    if (!comp[sum_all]) {          // S 自身是质数:全部数字放一个集合
        for (int i = 1; i <= n; i++) belong[i] = 1;
        output(n, 1);
        return 0;
    }

    // 找最小的质数 x 使 x 与 S-x 都是质数;找到了就能只拆两个集合
    ll pick = -1;
    for (ll x = 2; x <= sum_all / 2; x++) {
        if (!comp[x] && !comp[sum_all - x]) { pick = x; break; }
    }
    if (pick != -1) {
        for (int i = 1; i <= n; i++) belong[i] = 2;
        greedy_split(n, pick);     // 集合 1 凑出和 pick,集合 2 的和自然是 S-pick
        output(n, 2);
        return 0;
    }

    // 否则 S 是奇数且 S-2 是合数:取两个不同的质数 a、b 把 S-a-b 也凑成质数
    build_primes(n);
    ll selA = -1, selB = -1;
    for (int i = 1; i <= primeCnt && selA < 0; i++) {
        for (int j = 1; j <= primeCnt; j++) {
            if (primeList[j] == primeList[i]) continue;      // a、b 必须是两个不同的数
            if (!comp[sum_all - primeList[i] - primeList[j]]) {
                selA = primeList[i];
                selB = primeList[j];
                break;
            }
        }
    }

    if (selA < 0) {                // 理论上不会发生,保留兜底
        printf("-1\n");
        return 0;
    }
    for (int i = 1; i <= n; i++) belong[i] = 3;
    belong[selA] = 1;              // 集合 1 = {a}
    belong[selB] = 2;              // 集合 2 = {b},集合 3 的和 = S-a-b 是质数
    output(n, 3);

    return 0;
}

复杂度

记 S=n(n+1)2⩽18003000S = \frac{n(n+1)}{2} \leqslant 18003000。

  • 时间:埃氏筛 O(Slog⁡log⁡S)O(S \log \log S);寻找质数拆分与构造方案各 O(S)O(S)、O(n)O(n) 级别, 且实际只需枚举前几个小质数就能命中。总时间在 n=6000n = 6000 时仍是毫秒级。
  • 空间:筛表用 char / bytearray,为 O(S)O(S) 字节(约 1818 MB), 外加 O(n)O(n) 的归属数组,远低于 256256 MB。

总结

本题的"难"不在算法,而在敢不敢相信答案这么小。一旦把注意力从"怎么划分子集" 转到"SS 能写成几个质数之和",问题就被奇偶性一刀切成 −1/1/2/3-1/1/2/3 四个分支; 剩下的构造交给"连续整数上从大到小的贪心"这个稳定可用的工具。 这类题的通用经验是:先求答案的下界/上界结构,再考虑构造, 而不要一上来就写搜索或背包。

需要如实说明的一点:本题素材来自网络重建,随包的 data/ 由生成脚本按上述 四个分支分层自造(边界、最小三集合样本、中等规模直到 n=6000n = 6000), 并非官方评测数据;出题意图与原题可能略有偏差,但题面结论与三份公开题解一致。