584D - Dima and Lisa - CodeForces Solution

//ZedanPasha

#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define F first
#define S second
#define el '\n'
#define ss ' '
#define ll long long
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define rall(a) a.rbegin(),a.rend()
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define f(i, a, b)  for(int i = a; i < b; i++)
#define zedanPasha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using ii = pair<int, int>;
using ull = unsigned long long;

const ll MAX = 1e6 + 5;
const ll mod = 1e9 + 7;
const long double PI = acos(-1);
const long double EPS = 1e-7;

int dx[] = {0, 0, -1, 1};//right,left,up,down
int dy[] = {1, -1, 0, 0};

bool valid(int r, int c, int R, int C)
{
    if (r < 0 || r >= R || c < 0 || c >= C)
        return false;
    return true;
}

ll fp(int b, int p)
{
    //base,power
    if (p == 0)
        return 1;
    ll ans = fp(1LL * b * b % mod, p / 2);
    if (p % 2)
        return 1LL * ans * b % mod;
    return ans;
}

void sieve(int n)
{
    bitset<107> bs;
    bs.set();
    for (int i = 2; i <= n; i += 2)
        bs[i] = 0;
    for (int i = 3; (i * i) <= n; i += 2)
    {
        if (bs[i])
        {
            for (int j = i * i; j <= n; j += i)
                bs[j] = 0;
        }
    }
}

ll lcm(ll x, ll y)
{
    return (x * y) / __gcd(x, y);
}
bool prime(int n)
{
    if(n==2)
        return 1;
    if(n<=1 || n%2==0)
        return 0;
    for(int i=3  ; i*i<=n ; i+=2)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}
void doWork()
{
    ll n;
    cin>>n;
    if(n==3)
    {
        cout<<1<<el<<3;
        return;
    }
    if(n==5)
    {
        cout<<2<<el<<2<<ss<<3;
        return;
    }
    for(int i=n-3 ; i>=2 ; i--)
    {
        if(prime(i) && prime(n-i-3))
        {
            cout<<3<<el<<3<<ss<<n-i-3<<ss<<i;
            break;
        }
    }
}

int main()
{
    zedanPasha
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // online submission
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        doWork();
    return 0;
}