UVA 10168

solution.cpp

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

template <class T> int size(const T &x) {return x.size();}
template <class T> T mod(T a, T b) { return (b + (a % b)) % b;}

#define F first
#define S second
#define PB push_back
#define endl '\n'
#define rep(i, a, b) for(__typeof(a) i=a; i<(b); i++)
#define iter(it, c) for(__typeof((c).begin()) it=(c).begin(); \
 it != (c).end(); it++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;

const int INF = ~(1 << 31);
const double EPS = 1e-9;
const double PI = acos(-1);

const ll MX = 2e7 + 7;
bitset<MX> sieve;
vi primes;

void build() {
    sieve.set();
    sieve[0] = sieve[1] = 0;
    for (ll i = 2; i < MX; i++) {
        if (sieve[i]) {
            for (ll j = i * i; j < MX; j += i) sieve[j] = 0;
            primes.push_back((int)i);
        }
     }
}

void f(int n) {
    int o = n;
    if(n < 8) {
        cout << "Impossible." << endl;
        return;
    }

    int a, b = 2, c, d;
    for(int i=0; i<primes.size() && primes[i] < n; i++) {
        if((n - primes[i]) % 2 == 0) {
            a = primes[i];
            break;
        }
    }

    n -= a + 2;
    for(int i=0; i<primes.size() && primes[i] < n; i++) {
        if(sieve[n - primes[i]]) {
            c = n - primes[i];
            d = primes[i];
            break;
        }
    }

    printf("%d %d %d %d\n", a, b, c, d);

}

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

    build();
    int n;
    while(cin >> n)
        f(n);

    return 0;
}