https://www.luogu.org/problemnew/show/P1579
先预处理出素数看看有多少个,大概才2500个不到(事实上素数的个数大约是 $\frac{n}{ln(n)}$ ),所以他们两两组合不会超过 $10^7$ ,从小到大枚举所有的两两组合,算出第三个是不是素数即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long longint n;int num[];
int p[];
int ptop=;int init(){
num[]=;
for(int i=;i<=n;i++){
if(num[i]==){
p[ptop++]=i;
for(int j=i+i;j<=n;j+=i){
num[j]=;
}
}
} //cout<<ptop<<endl;
}int main(){
scanf("%d",&n);
init();
for(int i=;i<ptop;i++){
for(int j=i;j<ptop;j++){
int k=n-p[i]-p[j];
if(k>=&&num[k]==){
printf("%d %d %d\n",p[i],p[j],k);
return ;
}
}
}
}