0ms最快题解

# include <bits/stdc++.h>
typedef unsigned long long ull;

#define getchar getchar_unlocked()
#define psbc push_back
#define v vector
#define for1 for(i = 0;i<n;i++)

using  namespace  std ;
const int MX = 2e4;
int i,j,k;
int r(){
    int x = 0,f = 1;
    char c = getchar;
    while(c<'0'||c>'9'){if(c=='-') f = -1;c = getchar;}
    while(c>='0'&&c<='9') x = (x<<1)+(x<<3)+(c^(3<<4)),c = getchar;
    return x*f;
}
bool primevisited[MX];
int  main ( )
{
    for(i = 2;i<MX;i++) if(!primevisited[i]) for(j = i*i;j<MX;j += i) primevisited[j] = 1;
    int n = r();
    for(i = 2;i<=ceil(n/3.0);i++){
        if(!primevisited[i]){
            for(j = i;j<=ceil(n/2.0);j++){
                if(!primevisited[j]&&!primevisited[n-i-j]){
                    cout<<i<<" "<<j<<" "<<n-i-j;
                    return 0;
                }
            }
        }
    }
    return  0;
}

时间复杂度: $O(MX\ln(\ln(MX))+\frac{n^2}{6\ln(n^2)})$