# include < iostream >
bool isPrime ( int num) {
if (num <= 1 ) {
return false ;
}
for ( int i = 2 ; i * i <= num; i++) {
if (num % i == 0 ) {
return false ;
}
}
return true ;
}
void bt ( int solutie [], int k, int suma, int n) {
if (suma == n) {
for ( int i = 0 ; i < k; i++) {
std :: cout << solutie [i] << " " ;
}
std :: cout << std :: endl ;
} else {
for ( int i = (k > 0 ? solutie [k - 1 ] + 1 : 2 ); i <= n; i++) {
if ( isPrime (i) && suma + i <= n) {
solutie [k] = i;
bt ( solutie , k + 1 , suma + i, n);
}
}
}
}
int main () {
int n;
std :: cout << " Introduceti numarul natural n: " ;
std ::cin >> n;
int solutie [n];
bt ( solutie , 0 , 0 , n);
return 0 ;
}