You need to generate all the primes up to N using the sieve of Eratosthenes. (Only once)

You need to know what Goldbach conjecture is

Every even integer greater than 2 can be expressed as the sum of two primes.

Now to make the number even we need to choose the first two primes in such a way that the resultant number after removing this primes must be even

This implies
If the number is even select first two primes as 2 2
If the number is odd select first two primes as 2 3

Now you have an even number and you need to express it as a sum of two primes.

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

#if defined(DAIJOBU)
#include "/home/pavan/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}

bool ok[10000052];
vector<int> primes;
void sieve(){
	memset(ok , 1, sizeof ok);
	ok[0] = ok[1] = 0;
	for(int i = 2; i * i <= 10000050;i++){
		if(ok[i]){
			for(int j = i * i; j <= 10000050; j += i)ok[j] = 0;
		}
	}
	for(int i = 0; i <= 10000000;i++)if(ok[i])primes.push_back(i);
}

int main() {
	FIO

	sieve();
	int n;
	while(cin >> n){
		bool parity = n & 1, found = false;;
		n -= (4 + parity);
		for(auto i:primes){
			if(n - i >= 0 && ok[n - i]){
				found = true;
				if(parity)cout << "2 3 " << i << " " << n - i << "\n";
				else cout << "2 2 " << i << " " << n - i << "\n";
				break;
			}
		}
		if(!found)cout << "Impossible.\n";
	}
	return 0;
}