分享一下我的做法

之前没发过贴 也不知道怎么发代码

我的思路是线性筛然后判断题意范围内有2262个素数

然后暴力枚举 prime[i],prime[j] 只需要判断 n-prime[i]-prime[j]是不是素数就行

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20100;
int n,cnt;//表示maxn以内的素数个数
bool vis[maxn];
int prime[maxn];
void f()//线性筛 打表
{
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    vis[0] = vis[1] = 1;
    cnt = 0;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt && i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
void solve()
{
    for(int i=0;i<cnt;i++)
    {
        for(int j=i;j<cnt&& prime[j]+prime[i]<n;j++)
        {
            if(!vis[n-prime[i]-prime[j]]){
                cout<< prime[i]<<" "<<prime[j]<<" "<<n-prime[i]-prime[j]<<endl;
                return;
            }
        }
    }
}
int main ()
{
    //freopen("out.txt","w",stdout);
    cin >> n;
    f();//发现有2262个素数 可以n2处理
    solve();
    return 0;
}