p116.ans1
======================
2
3 3

=================
p116.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

vector<int> super_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    int cnt = 0;
    vector<int> res;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) {
            cnt++;
            if(is_prime[cnt]) {
                res.push_back(i);
            }

            for(int64_t j = i * 1ll * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return res;
}

vector<int> sp;
int n;

void read() { cin >> n; }

void solve() {
    // A super-prime is the k-th prime where k itself is prime. We precompute
    // all super-primes by sieving and checking that the prime's index is
    // prime. Then this is an unbounded coin-change: dp[j] = fewest super-primes
    // summing to j (-1 if impossible). We reconstruct one optimal multiset by
    // greedily peeling off a super-prime that keeps dp on an optimal path, and
    // print the summands in non-increasing order.

    vector<int> dp(n + 1, -1);
    dp[0] = 0;
    for(int i = 0; i < (int)sp.size(); i++) {
        for(int j = sp[i]; j <= n; j++) {
            if(dp[j - sp[i]] != -1) {
                if(dp[j] == -1 || dp[j - sp[i]] + 1 < dp[j]) {
                    dp[j] = dp[j - sp[i]] + 1;
                }
            }
        }
    }

    if(dp[n] == -1) {
        cout << 0 << '\n';
        return;
    }

    vector<int> ans;
    while(n > 0) {
        for(int i = 0; i < (int)sp.size(); i++) {
            if(n >= sp[i] && dp[n - sp[i]] == dp[n] - 1) {
                ans.push_back(sp[i]);
                n -= sp[i];
                break;
            }
        }
    }

    cout << ans.size() << '\n';
    sort(ans.rbegin(), ans.rend());
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    sp = super_primes((int)1e6);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p116.in1
======================
6

=================
statement.txt
======================
116. Index of super-prime

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Let P1, P2, … ,PN, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes.


Input

There is a positive integer number in input. Number is not more than 10000.


Output

Write index I for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing.


Sample Input

6
Sample Output

2
3 3
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

=================
