总和 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
形式化题目
给定
要求输出最小的
数据规模:
方案不唯一,只要
正解
思路
先把"最少集合数"和"怎么凑出这些集合"拆成两件事,因为它们各自有非常不同的抓手。
第一步:答案
时 。 既不是质数,也没有别的数可以帮它凑,只能输出 。 这是唯一的无解情形。 本身是质数时取 ,把 全放进一个集合。 是质数只发生在 ( ),其余 试一下就知道。 - 否则看
能否写成两个质数之和。这里要分奇偶: 为偶数:由哥德巴赫猜想(在本题 的范围内已被完全 验证),任何大于 的偶数都等于两个质数之和,所以 必然可行。 为奇数:两个整数和为奇数必须一奇一偶,而唯一的偶质数是 ,因此形式只能是 。于是只要检查 是不是质数即可。
- 上一条不成立时(
为奇数且 为合数): 是偶数,同样由哥德巴赫猜想 可以拆成两个质数 ,再加上质数 就有 。 所以 恒成立。
这就把问题从"搜子集"变成了"数论判别 + 构造":答案只可能是
第二步:怎么把目标和摊到具体的数上。
确定
两个分支因此落地为:
:先找一对质数 与 ( 偶时从最小的质数往上试即可命中; 奇时只能是 )。把所有数默认放进集合 2,再用贪心把和为 的那组挪进集合 1, 集合 2 的和自动是 。 :枚举两个互不相同的质数 使 仍为质数, 把 、 各单独成一个集合,剩下的数全塞进第三个集合,其和恰为 。 由哥德巴赫弱形式(任一大于 的整数可写成三个质数之和)知这样的 存在, 代码里从最小的质数往上找即可。
代码
Python 短解法与 C++ 同阶:都是埃氏筛 bytearray 切片赋值把内层循环交给 C 实现。
#!/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++ 版本把筛表、质数表和归属数组都放在全局,避免大数组压栈;
long long 参与乘法,避免中途溢出。
/**
* 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;
}复杂度
记
- 时间:埃氏筛
;寻找质数拆分与构造方案各 、 级别, 且实际只需枚举前几个小质数就能命中。总时间在 时仍是毫秒级。 - 空间:筛表用
char/bytearray,为字节(约 MB), 外加 的归属数组,远低于 MB。
总结
本题的"难"不在算法,而在敢不敢相信答案这么小。一旦把注意力从"怎么划分子集"
转到"
需要如实说明的一点:本题素材来自网络重建,随包的 data/ 由生成脚本按上述
四个分支分层自造(边界、最小三集合样本、中等规模直到