台北市104 學年度資訊學科能力競賽 pA. Prime ( 神秘暴搜 )

時間複雜度很神秘混沌的題目。竟然這樣暴搜就可以過了。如果有人可以提出證明它是好/壞的，請務必告訴我。
用質數篩法把質數表先建出來後，對每次的詢問進行遞迴求解，無需剪枝。
注意不能減去比當前的數字大的質數，你會花很久時間才發現你是怎麼逾時的。

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

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > pii;

const int MAXM = 1e6 + 6;

int np[ MAXM ];
vi prime;

void init(){
    np[ 0 ] = np[ 1 ] = 1;
    for( int i = 2; i < MAXM; ++i )
        if( not np[ i ] ){
            for( int j = i + i; j < MAXM; j += i )
                np[ j ] = 1;
            prime.push_back( i );
        }
}

bool dfs( int x, int f, vi &ans ){
    if( x == 0 )
        return true;
    if( f < 0 )
        return false;
    while( f > 0 and prime[ f ] > x ) --f;
    for( int i = f; i >= 0; --i ){
        ans.push_back( prime[ i ] );
        if( dfs( x - prime[ i ], i - 1, ans ) )
            return true;
        ans.pop_back();
    }
    return false;
}

void solve(){
    int T; cin >> T;
    while( T-- ){
        int M; cin >> M;
        if( np[ M ] ){
            cout << 0 << endl;
            continue;
        }
        int f = lower_bound( prime.begin(), prime.end(), M ) - prime.begin();
        vi ans;
        if( not dfs( M, f - 1, ans ) ){
            cout << M << endl;
            continue;
        }
        for( int i = 0; i < ans.size(); ++i )
            cout << ans[ i ] << " \n"[ i + 1 == ans.size() ];
    }
}

signed main(){
    ios::sync_with_stdio( false );
    init();
    solve();
    return 0;
}