（水题）洛谷

https://www.luogu.org/problemnew/show/P1579

先预处理出素数看看有多少个，大概才2500个不到（事实上素数的个数大约是 $frac{n}{ln(n)}$ ），所以他们两两组合不会超过 $10^7$ ，从小到大枚举所有的两两组合，算出第三个是不是素数即可。

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

int n;

int num[20000005];
int p[20000005];
int ptop=0;

int init(){
    num[1]=1;
    for(int i=2;i<=n;i++){
        if(num[i]==0){
            p[ptop++]=i;
            for(int j=i+i;j<=n;j+=i){
                num[j]=1;
            }
        }
    }

    //cout<<ptop<<endl;
}


int main(){
    scanf("%d",&n);
    init();
    for(int i=0;i<ptop;i++){
        for(int j=i;j<ptop;j++){
            int k=n-p[i]-p[j];
            if(k>=1&&num[k]==0){
                printf("%d %d %d
",p[i],p[j],k);
                return 0;
            }
        }
    }
}