思路与算法

筛到总和S=n(n+1)/2。若S素则全部一组；若S合数为偶数，枚举两个素数分解；若S为奇数且S-2素，用2及S-2两组。余下奇数情形至少三组，先把数字3单列，再把S-3分成两素数。对所需素数和，用从大到小取数构造其子集，剩余数为另一组。

正确性说明

一组当且仅当总和为素数。奇数分成两个素数时必有一个为2，所以S-2不素时两组不可能。剩余偶数在本题有限范围内通过筛表枚举找到素数对，不依赖未证明的一般Goldbach猜想。1至n可表示每个0至S的和；三组时删去3后1,2,4,…,n仍满足每个数不超过此前总和加1，因而下降贪心仍表示任意所需和。构造给出与下界一致的1/2/3组。

复杂度

筛表初始化与筛O(SloglogS)，寻找素数对最坏O(S)，子集构造O(n)，空间O(S)位的vector加O(n)分组，S≤18003000。

易错点

n=1总和1不素且无法拆出素数，输出-1。每个数字恰分到一组、各组和必须是素数。多解特判核对全部组及最少组数，不要求与参考分组标签相同。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int S = n * (n + 1) / 2;
    vector<bool> com(S + 1);
    if (S >= 0)
        com[0] = true;
    if (S >= 1)
        com[1] = true;
    for (int i = 2; i * i <= S; i++)
        if (!com[i])
            for (int j = i * i; j <= S; j += i)
                com[j] = true;
    if (n == 1) {
        cout << "-1\n";
        return 0;
    }
    vector<int> grp(n + 1, 1);
    int count = 1, target = 0, skip = -1;
    if (com[S]) {
        count = 2;
        if (S % 2) {
            if (!com[S - 2])
                target = 2;
            else {
                count = 3;
                skip = 3;
                grp[3] = 1;
                int rem = S - 3;
                for (int p = 2; p <= rem; p++)
                    if (!com[p] && !com[rem - p]) {
                        target = p;
                        break;
                    }
                for (int i = 1; i <= n; i++)
                    if (i != 3)
                        grp[i] = 3;
            }
        } else {
            for (int p = 2; p <= S; p++)
                if (!com[p] && !com[S - p]) {
                    target = p;
                    break;
                }
        }
        if (count == 2)
            fill(grp.begin() + 1, grp.end(), 2);
        for (int i = n; i >= 1; i--)
            if (i != skip && i <= target) {
                grp[i] = count == 2 ? 1 : 2;
                target -= i;
            }
        if (target) {
            cout << "-1\n";
            return 0;
        }
    }
    cout << count << '\n';
    for (int i = 1; i <= n; i++)
        cout << grp[i] << (i == n ? '\n' : ' ');
}