(原题链接)[http://47.110.142.74/contest/1681/problem/0]
题意：
给一个数n，序列为1~n。现在将序列分为k组，使得每组内数的和都为质数并且k最小。如果k相等的话，优先输出第一个数小的。
思路：
哥德巴赫猜想，偶数可以写成两个素数的和，奇数可以写成三个素数的和。这是一定的。
题目限制k最小，所以应该先考虑奇数是否能写成两个素数的和。
相当于对1+2+……+n进行判断，筛完素数后，枚举其中一个或两个，判断是否合理即可。
注意特判几种情况，比如n为2的时候。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} #define PI acos(-1) #define x first #define y second const int N=1e7+7; int pri[N],cnt; bool st[N]; void prim(int x){ for(int i=2;i<=x;i++){ if(!st[i]) pri[cnt++]=i; for(int j=0;pri[j]<=x/i;j++){ st[pri[j]*i]=true; if(i%pri[j]==0) break; } } } int main(){ prim(1e7); ll n=read; if(!n||n==1){ puts("-1"); return 0; } if(n==2){ puts("1"); puts("3"); return 0; } n=(n+1)*n/2; if(n%2==0){ puts("2"); for(int i=0;i<cnt;i++) if(n-pri[i]>0&&!st[n-pri[i]]){ int a[2]; a[0]=pri[i],a[1]=n-pri[i]; //sort(a,a+1); printf("%d %d\n",a[0],a[1]); return 0; } } else{ bool flag=0; for(int i=0;i<cnt;i++) if(n-pri[i]>0&&!st[n-pri[i]]){ int a[2]; a[0]=pri[i],a[1]=n-pri[i]; //sort(a,a+1); printf("2\n%d %d\n",a[0],a[1]); flag=1; return 0; } if(flag) return 0; puts("3"); for(int i=0;i<cnt;i++) for(int j=i;j<cnt;j++) if(n-pri[i]-pri[j]>0&&!st[n-pri[i]-pri[j]]){ int a[3]; a[0]=pri[i],a[1]=pri[j],a[2]=n-pri[i]-pri[j]; // sort(a,a+2); printf("%d %d %d\n",a[0],a[1],a[2]); return 0; } } return 0; }
