Fundamente XI - 8 / 219

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int NMAX = 1e4 + 4;
bitset < NMAX > sieve;

void Eratostene() {
    sieve[0] = sieve[1] = true;
    for(int i = 4; i <= 10000; i += 2)
        sieve[i] = true;
    for(int i = 3; i * i <= 10000; i += 2)
        if(!sieve[i])
            for(int j = i * i; j <= 10000; j += 2 * i)
                sieve[j] = true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    Eratostene();
    int index = 1;
    vector < int > a;
    for(int i = 3; i < 10000; i += 2)
        if(!sieve[i]) {
            ++index;
            if(!sieve[index])
                a.emplace_back(i);
        }
    vector < int > dp(N + 1, INF), t(N + 1);
    dp[0] = 0;
    for(int i = 1; i <= N; ++i)
        for(int x : a)
            if(i - x >= 0 && dp[i] > dp[i - x] + 1) {
                dp[i] = dp[i - x] + 1;
                t[i] = x;
            }
    cout << dp[N] << '\n';
    vector < int > sol;
    while(N > 0) {
        sol.emplace_back(t[N]);
        N -= t[N];
    }
    reverse(sol.begin(), sol.end());
    for(int x : sol)
        cout << x << ' ';
}