descprime

#include <bits/stdc++.h>

int a[105], sol[105], mx_steps = -1, rez[105], nr, c, n;
bool P[105], used[105];

void Eratostene() { // Am facut Eratostene pana la 100.
    P[0] = P[1] = 1;
    for(int i = 2; i * i <= 100; ++i)
        if(P[i] ==0)
            for(int j = 2; i * j <= 100; ++j)
                P[i * j] = 1;
    a[++c] = 2;
    poz[c] = 1;
    for(int i = 3; i <= 97; i+=2) // Mi-am pus toate numerele prime intr-un vector pe care o sa-l parcurg.
        if(P[i] == 0)
            a[++c] = i;
}


void result(int step){
    if(rez[1] == 0){ // verifica daca vectorul rezultat e gol. (daca e gol, pun direct solutia in el)
        for(int i = 1; i <= step - 1; ++i)
            rez[i] = sol[i];
    }
    else {
        bool ok = 1;
        for(int i = 1; i <= step - 1; ++i) // verific daca e minim lexicografic
            if(sol[i] > rez[i]){
                ok = 0;
                break;
            }
        if(ok){
            for(int i = 1; i <= step - 1; ++i)
                rez[i] = sol[i];
        }
    }
}

bool check(int step){
    for(int i = 1; i < step - 1; ++i) // verific daca vectorul solutie este ordonat crescator
        if(sol[i] > sol[i+1])
            return 0;
    return 1;
}

void back(int step, int S){
    if(S == n && check(step)){ // Daca suma == n si daca vectorul solutie e crescator.
        nr++; // am gasit o solutie.
        if(step - 1 > mx_steps){ // (maximul de pasi)
            mx_steps = step - 1;
            result(step);
        }
        else if(step - 1 == mx_steps) // daca e adevarata, verifica daca vec sol e mai mic lexicografic ca vectorul rezultat
            result(step);
    }
    else if(S > n) // daca trec cu suma de n ies din recursie
        return ;

    for(int i = 1; i <= c; ++i){
        sol[step] = a[i];
        if(used[a[i]] == 0){ // daca nu am mai folosit acel numar prim
            used[a[i]] = 1; // il marchez ca fiind folosit
            back(step + 1, S + a[i]); // intru in recursie cu el ca fiind folosit
            used[a[i]] = 0; // cand ies din recursie, il fac la loc 0 ca sa l pot folosi in alte solutii.
        }
    }
}

int main()
{
    Eratostene();
    std::cin >> n;
    back(1, 0);
    std::cout  << nr << '\n';
    for(int i = 1; i <= mx_steps; ++i)
        std::cout << rez[i] << " ";
    return 0;
}